📑 题目：169. 多数元素

🚀 本题 LeetCode 传送门

题目大意

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。

解题思路

• 题目要求找出数组中出现次数大于 ⌊ n/2 ⌋ 次的数。要求空间复杂度为 O(1)。简单题。
• 这一题利用的算法是 Boyer-Moore Majority Vote Algorithm。 https://www.zhihu.com/question/49973163/answer/235921864

代码

package leetcode
// 解法一 时间复杂度 O(n) 空间复杂度 O(1)
func majorityElement(nums []int) int {
 res, count := nums[0], 0
 for i := 0; i < len(nums); i++ {
  if count == 0 {
   res, count = nums[i], 1
  } else {
   if nums[i] == res {
    count++
   } else {
    count--
   }
  }
 }
 return res
}
// 解法二 时间复杂度 O(n) 空间复杂度 O(n)
func majorityElement1(nums []int) int {
 m := make(map[int]int)
 for _, v := range nums {
  m[v]++
  if m[v] > len(nums)/2 {
   return v
  }
 }
 return 0
}