1.两数之和(1) 代码语言： javascript
复制 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] nums[1] == 9 ，返回 [0, 1]代码语言： javascript
复制 //暴力解法
//时间复杂度：O(N²)
//空间复杂度：O(1)
func twoSum1(nums []int, target int) []int {
for i, v := range nums{
for j := i 1; j < len(nums); j {
sum := v nums[j]
if sum == target {
return []int{i, j}
}
}
}
return nil
}
//查找表法
//用map记录已经遍历过的数值和下标
//空间换时间
//时间复杂度：O(N)
//空间复杂度：O(N)
func twoSum2(nums []int, target int) []int {
//mapTemp := map[int]int{}
mapTemp := make(map[int]int, len(nums)) //初始化一定内存，内存消耗更少
for i, v := range nums {
if j, ok := mapTemp[target-v]; ok {
return []int{j, i}
}
mapTemp[v] = i
}
return nil
}
func main() {
nums := []int{2, 7, 11, 15}
target := 9
result1 := twoSum1(nums, target)
fmt.Println(result1)
result2 := twoSum2(nums, target)
fmt.Println(result2)
}2.有效的括号(20) 代码语言： javascript
复制 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()[]{}"
输出：true
示例 2：
输入：s = "{[]}"
输出：true
示例 3：
输入：s = "([)]"
输出：false代码语言： javascript
复制 //时间复杂度：O(N)
//空间复杂度：O(N E)，E表示括号的个数
//栈的思想
func isValid(s string) bool {
if len(s)%2 == 1 {
return false
}
mapTemp := map[byte]byte{
')': '(',
']': '[',
'}': '{',
}
var stack []byte
for i := 0; i < len(s); i {
if v, ok := mapTemp[s[i]]; ok {
if len(stack) == 0 || stack[len(stack)-1] != v {
return false
}
stack = stack[:len(stack)-1]
} else {
stack = append(stack, s[i])
}
}
return len(stack) == 0
}
func main() {
s := "()[]{}"
b := isValid(s)
fmt.Println(b)
}3.合并两个有序链表(21) 代码语言： javascript
复制 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1:
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]代码语言： javascript
复制 type ListNode struct {
Val int
Next *ListNode
}
//递归法
func mergeTwoLists1(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
var result *ListNode
if l1.Val <= l2.Val {
result = l1
result.Next = mergeTwoLists1(l1.Next, l2)
} else {
result = l2
result.Next = mergeTwoLists1(l1, l2.Next)
}
return result
}
//迭代法
//会比用递归占用更少的空间
func mergeTwoLists2(l1 *ListNode, l2 *ListNode) *ListNode {
nodeTemp := &ListNode{}
current := nodeTemp
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
current.Next = l1
l1 = l1.Next
} else {
current.Next = l2
l2 = l2.Next
}
current = current.Next
}
if l1 != nil {
current.Next = l1
} else {
current.Next = l2
}
return nodeTemp.Next
}
func main() {
var h1 = new(ListNode)
h1.Val = 1
var h2 = new(ListNode)
h2.Val = 2
var h3 = new(ListNode)
h3.Val = 4
h1.Next = h2
h2.Next = h3
h3.Next = nil
var h11 = new(ListNode)
h11.Val = 1
var h22 = new(ListNode)
h22.Val = 3
var h33 = new(ListNode)
h33.Val = 4
h11.Next = h22
h22.Next = h33
h33.Next = nil
//result1 := mergeTwoLists1(h1, h11)
//fmt.Println(result1)
result2 := mergeTwoLists2(h1, h11)
fmt.Println(result2)
}4.最大子序和(53) 代码语言： javascript
复制 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6
示例 2：
输入：nums = [1]
输出：1代码语言： javascript
复制 //动态规划
//f(i)表示以第i个数结尾的最大连续和
//f(i)=max{f(i−1) nums[i],nums[i]}
//时间复杂度：O(n)，其中 n 为 nums 数组的长度，我们只需要遍历一遍数组即可求得答案
//空间复杂度：O(1)，我们只需要常数空间存放若干变量
func maxSubArray(nums []int) int {
max := nums[0]
for i := 1; i < len(nums); i {
/*
凡是会让总数变小的值，即<0的值，一律丢弃，
这里也可以写成：
if nums[i-1] > 0 {
nums[i] = nums[i-1]
}
*/
if nums[i-1] nums[i] > nums[i] {
nums[i] = nums[i-1]
}
if max < nums[i] {
max = nums[i]
}
}
return max
}
func main() {
nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
result := maxSubArray(nums)
fmt.Println(result)
}5.爬楼梯(70) 代码语言： javascript
复制 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 1 阶 1 阶
2. 1 阶 2 阶
3. 2 阶 1 阶代码语言： javascript
复制 //暴力递归，动态规划
//转移方程：f(x) = f(x-1) f(x-2)
//时间复杂度：O(2ⁿ)
//空间复杂度：O(n)
func climbStairs1(n int) int {
if n == 1 {
return 1
}
if n == 2 {
return 2
}
return climbStairs1(n-1) climbStairs1(n-2)
}
//记忆化递归，动态规划
//把已经用过的楼梯数保存起来直接返回，减少递归次数
//时间复杂度：O(n)
//空间复杂度：O(n)
func climbStairs2(n int) int {
memo := make([]int, n 1, n 1)
return climbStairsMemo(n, memo)
}
func climbStairsMemo(n int, memo []int) int {
if memo[n] > 0 {
return memo[n]
}
if n == 1 {
memo[n] = 1
} else if n == 2 {
memo[n] = 2
} else {
memo[n] = climbStairsMemo(n-1, memo) climbStairsMemo(n-2, memo)
}
return memo[n]
}
//优化空间复杂度后的动态规划
//滚动数组思想
//时间复杂度：O(n)
//空间复杂度：O(1)
func climbStairs3(n int) int {
p, q, r := 0, 0, 1
for i := 0; i < n; i {
p = q
q = r
r = p q
}
return r
}
func main() {
n := 10
result1 := climbStairs1(n)
fmt.Println(result1)
result2 := climbStairs2(n)
fmt.Println(result2)
result3 := climbStairs3(n)
fmt.Println(result3)
}6.二叉树的中序遍历(94) 代码语言： javascript
复制 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 1 阶 1 阶
2. 1 阶 2 阶
3. 2 阶 1 阶代码语言： javascript
复制 type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
//递归法
//时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
//空间复杂度：O(n)，空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
func inorderTraversal1(root *TreeNode) (res []int) {
var inorder func(node *TreeNode)
inorder = func(node *TreeNode) {
if node != nil {
inorder(node.Left)
res = append(res, node.Val)
inorder(node.Right)
}
return
}
inorder(root)
return
}
//迭代法
//时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
//空间复杂度：O(n)，空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。
func inorderTraversal2(root *TreeNode) (res []int) {
var stack []*TreeNode
for root != nil || len(stack) > 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, root.Val)
root = root.Right
}
return
}
func main() {
var root = new(TreeNode)
var root1 = new(TreeNode)
var root2 = new(TreeNode)
root.Val = 1
root.Left = nil
root.Right = root1
root1.Val = 2
root1.Right = nil
root1.Left = root2
root2.Val = 3
root2.Left = nil
root2.Right = nil
a := inorderTraversal1(root)
fmt.Println(a)
b := inorderTraversal2(root)
fmt.Println(b)
}7.对称二叉树(101) 代码语言： javascript
复制 给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/
2 2
/ /
3 4 4 3
但是下面这个[1,2,2,null,3,null,3] 则不是镜像对称的:
1
/
2 2
3 3代码语言： javascript
复制 type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
//递归法
//时间复杂度：O(n)
//空间复杂度：O(n)
/*可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，
pp 指针和 qq 指针一开始都指向这棵树的根，随后 pp 右移时，qq 左移，pp 左移时，qq 右移。
每次检查当前 pp 和 qq 节点的值是否相等，如果相等再判断左右子树是否对称*/
func isSymmetric1(root *TreeNode) bool {
return check(root, root)
}
func check(p, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil {
return false
}
return p.Val == q.Val && check(p.Left, q.Right) && check(p.Right, q.Left)
}
//迭代法
//时间复杂度：O(n)
//空间复杂度：O(n)
//用队列模拟递归的实现
func isSymmetric2(root *TreeNode) bool {
u, v := root, root
var queue []*TreeNode
queue = append(queue, u)
queue = append(queue, v)
for len(queue) > 0 {
u, v = queue[0], queue[1]
queue = queue[2:]
if u == nil && v == nil {
continue
}
if u == nil || v == nil {
return false
}
if u.Val != v.Val {
return false
}
queue = append(queue, u.Left)
queue = append(queue, v.Right)
queue = append(queue, u.Right)
queue = append(queue, v.Left)
}
return true
}
func main() {
var n1 = new(TreeNode)
var n2 = new(TreeNode)
var n3 = new(TreeNode)
var n4 = new(TreeNode)
var n5 = new(TreeNode)
var n6 = new(TreeNode)
var n7 = new(TreeNode)
n1.Val = 1
n2.Val = 2
n3.Val = 2
n4.Val = 3
n5.Val = 4
n6.Val = 4
n7.Val = 3
n1.Left = n2
n1.Right = n3
n2.Left = n4
n2.Right = n5
n3.Left = n6
n3.Right = n7
result1 := isSymmetric1(n1)
fmt.Println(result1)
result2 := isSymmetric2(n1)
fmt.Println(result2)
}8.二叉树的最大深度(104) 代码语言： javascript
复制 给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明:叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度3代码语言： javascript
复制 type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func max(a, b int) int {
if a < b {
return b
}
return a
}
//深度优先搜索
//时间复杂度：O(n)
//空间复杂度：O(height)
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return max(maxDepth(root.Left), maxDepth(root.Right)) 1
}
//广度优先搜索
//时间复杂度：O(n)
//空间复杂度：最坏情况O(n)
func maxDepth1(root *TreeNode) int {
if root == nil {
return 0
}
var queue []*TreeNode
queue = append(queue, root)
ans := 0
for len(queue) > 0 {
sz := len(queue)
for sz > 0 {
node := queue[0]
queue = queue[1:]
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
sz--
}
ans
}
return ans
}
func main() {
var root = new(TreeNode)
var root1 = new(TreeNode)
var root2 = new(TreeNode)
var root3 = new(TreeNode)
var root4 = new(TreeNode)
root.Val = 3
root.Left = root1
root.Right = root2
root1.Val = 9
root2.Val = 20
root2.Left = root3
root2.Right = root4
root3.Val = 15
root4.Val = 7
fmt.Println(maxDepth(root))
fmt.Println(maxDepth1(root))
}9.买卖股票的最佳时机(121) 代码语言： javascript
复制 给定一个数组 prices ，它的第i 个元素prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。代码语言： javascript
复制 //时间复杂度：O(n)
//空间复杂度：O(1)
func maxProfit(prices []int) int {
maxNum := 0
tempMaxNum := 0
min := prices[0]
for i := 1; i < len(prices); i {
if prices[i] < min {
min = prices[i]
}
tempMaxNum = prices[i] - min
if tempMaxNum > maxNum {
maxNum = tempMaxNum
}
}
return maxNum
}
func main() {
prices := []int{7, 1, 5, 3, 6, 4}
fmt.Println(maxProfit(prices))
pricess := []int{7, 6, 4, 3, 1, 0}
fmt.Println(maxProfit(pricess))
fmt.Println(math.MaxInt64)
fmt.Println(math.MinInt64)
}10.只出现一次的数字(136) 代码语言： javascript
复制 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例2:
输入: [4,1,2,1,2]
输出: 4代码语言： javascript
复制 //时间复杂度：O(n)
//空间复杂度：O(n)
func singleNumber(nums []int) int {
repeate := make(map[int]bool)
for i := 0; i < len(nums); i {
_, exist := repeate[nums[i]]
if exist {
repeate[nums[i]] = true
} else {
repeate[nums[i]] = false
}
}
for i := 0; i < len(nums); i {
if repeate[nums[i]] == false {
return nums[i]
}
}
return 0
}
//时间复杂度：O(n)
//空间复杂度：O(n)
func singleNumber1(nums []int) int {
repeate := make(map[int]bool)
final := 0
for i := 0; i < len(nums); i {
if _, exist := repeate[nums[i]]; !exist {
repeate[nums[i]] = true
final = nums[i]
} else {
final -= nums[i]
}
}
return final
}
//异或
//时间复杂度：O(n)
//空间复杂度：O(1)
func singleNumber2(nums []int) int {
s := 0
for i:=0; i<len(nums); i {
s = s ^ nums[i]
}
return s
}
func main() {
a := []int{4, 1, 2, 1, 2}
fmt.Println(singleNumber(a))
fmt.Println(singleNumber1(a))
fmt.Println(singleNumber2(a))
}11.环形链表(141) 代码语言： javascript
复制 给一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
示例：
输入：head = [3,2,0,-4]，pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点代码语言： javascript
复制 type ListNode struct {
Val int
Next *ListNode
}
//方法一：哈希表法
//每到达一个节点，若该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中
//时间复杂度：O(n)
//空间复杂度：O(n)
func hasCycle1(head *ListNode) bool {
tempMap := map[*ListNode]struct{}{}
for head != nil {
if _, ok := tempMap[head]; ok {
return true
}
tempMap[head] = struct{}{}
head = head.Next
}
return false
}
//方法二：快慢指针法
//一个慢指针每次移动一步，一个快指针一次移动两步，当快指针追上慢指针后说明存在环
//时间复杂度：O(n)
//空间复杂度：O(1)
func hasCycle2(head *ListNode) bool {
if head == nil || head.Next == nil {
return false
}
slow, fast := head, head.Next
for slow != fast {
if fast == nil || fast.Next == nil {
return false
}
slow = slow.Next
fast = fast.Next.Next
}
return true
}
func main() {
node1 := new(ListNode)
node2 := new(ListNode)
node3 := new(ListNode)
node4 := new(ListNode)
node1.Val = 3
node1.Next = node2
node2.Val = 2
node2.Next = node3
node3.Val = 0
node3.Next = node4
node4.Val = -4
node4.Next = node2
cycle1 := hasCycle1(node1)
fmt.Println(cycle1)
cycle2 := hasCycle2(node1)
fmt.Println(cycle2)
}12.最小栈(155) 代码语言： javascript
复制 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop()—— 删除栈顶的元素。
top()—— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
思路：
对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，
只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。
因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么就可以确定栈里面现在的元素一定是 a, b, c, d。
那么，可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，
就可以直接返回存储的最小值 m代码语言： javascript
复制 //时间复杂度：O(1)
//空间复杂度：O(n)
type MinStack struct {
stack []int
minStack []int
}
func Constructor() MinStack {
return MinStack{
stack: []int{},
minStack: []int{math.MaxInt64},
}
}
func (this *MinStack) Push(x int) {
this.stack = append(this.stack, x)
top := this.minStack[len(this.minStack)-1]
this.minStack = append(this.minStack, min(x, top))
}
func (this *MinStack) Pop() {
this.stack = this.stack[:len(this.stack)-1]
this.minStack = this.minStack[:len(this.minStack)-1]
}
func (this *MinStack) Top() int {
return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
return this.minStack[len(this.minStack)-1]
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
func main() {
}13.相交链表(160)# 代码语言： javascript
复制 给两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点，
如果两个链表不存在相交节点，返回 null。
题目保证整个链式结构中不存在环，且函数返回结果后，链表必须保持其原始结构
设计一个时间复杂度 O(m n) 、仅用 O(1) 内存的解决方案代码语言： javascript
复制 type ListNode struct {
Val int
Next *ListNode
}
//哈希集合法
//思路：遍历链表headA，并将链表headA中的每个节点加入哈希集合中，
//然后遍历链表headB，对于遍历到的每个节点，判断该节点是否在哈希集合中。
//时间复杂度：O(m n)
//空间复杂度：O(n)
func getIntersectionNode1(headA, headB *ListNode) *ListNode {
tempMap := map[*ListNode]bool{}
for tmp := headA; tmp != nil; tmp = tmp.Next {
tempMap[tmp] = true
}
for tmp := headB; tmp != nil; tmp = tmp.Next {
if tempMap[tmp] {
return tmp
}
}
return nil
}
//双指针法
//时间复杂度：O(m n)
//空间复杂度：O(1)
func getIntersectionNode2(headA, headB *ListNode) *ListNode {
if headA == nil || headB == nil {
return nil
}
pa, pb := headA, headB
for pa != pb {
if pa == nil {
pa = headB
} else {
pa = pa.Next
}
if pb == nil {
pb = headA
} else {
pb = pb.Next
}
}
return pa
}
func main() {
}14.多数元素(169) 代码语言： javascript
复制 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋的元素。
可以假设数组是非空的，并且给定的数组总是存在多数元素。
设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题
示例1：
输入：[3,2,3]
输出：3
示例2：
输入：[2,2,1,1,1,2,2]
输出：2代码语言： javascript
复制 //哈希表法
//元素作为key，个数作为value，根据value最大的那个选择key对应的元素即是结果
//时间复杂度：O(n)
//空间复杂度：O(n)
func majorityElement1(nums []int) int {
tempMap := map[int]int{}
max := math.MinInt
final := 0
for _, v := range nums {
if _, ok := tempMap[v]; ok {
tempMap[v]
} else {
tempMap[v] = 1
}
}
for k, v := range tempMap {
if v > max {
max = v
final = k
}
}
return final
}
//排序法
//如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，
//那么下标为 ⌊ n/2 ⌋ 的元素（下标从 0 开始）一定是众数
//时间复杂度：O(nlogn)，将数组排序的时间复杂度为 O(nlogn)
//空间复杂度：O(logn)
func majorityElement2(nums []int) int {
sort.Ints(nums)
return nums[len(nums)/2]
}
//随机化法
//因为超过 ⌊n/2⌋ 的数组下标被众数占据了，这样随机挑选一个下标对应的元素并验证，有很大的概率能找到众数
//时间复杂度：理论上最坏情况下的时间复杂度为 O(∞)，期望的时间复杂度为 O(n)
//空间复杂度：O(1)
func majorityElement3(nums []int) int {
for {
randIndex := rand.Intn(len(nums))
candidate := nums[randIndex]
count := 0
for i := 0; i < len(nums); i {
if nums[i] == candidate {
count
if count > len(nums)/2 {
return nums[i]
}
}
}
}
}
//投票算法
//维护一个候选众数 candidate 和它出现的次数 count
//遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，先将 x 的值赋予 candidate，随后判断 x：
//如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
//如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
//在遍历完成后，candidate 即为整个数组的众数
//时间复杂度：O(n)
//空间复杂度：O(1)
func majorityElement4(nums []int) int {
count := 0
candidate := 0
for i := 0; i < len(nums); i {
if count == 0 {
candidate = nums[i]
}
if candidate == nums[i] {
count
} else {
count--
}
}
return candidate
}
func main() {
s := []int{2, 2, 1, 1, 1, 2, 2}
fmt.Println(majorityElement1(s))
fmt.Println(majorityElement2(s))
fmt.Println(majorityElement3(s))
fmt.Println(majorityElement4(s))
}
