169.多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
解题思路：
- 哈希表：时间复杂度 O(n)，空间复杂度 O(n)
- 排序: 时间复杂度 O(nlogn)，空间复杂度 O(1)
- Boyer-Moore 投票算法（最优解）
// 哈希表：时间复杂度 O(n)，空间复杂度 O(n)
func majorityElement(nums []int) int {
m := len(nums) / 2
var mp = make(map[int]int)
for _, num := range nums {
mp[num] += 1
if mp[num] > m {
return num
}
}
return 0
}
// 排序: 时间复杂度 O(nlogn)，空间复杂度 O(1)
func majorityElement1(nums []int) int {
sort.Ints(nums)
return nums[len(nums)/2]
}
/*
Boyer-Moore 投票算法（最优解）
核心思想：维护一个候选元素和计数器
- 遇到相同元素计数加1，不同元素计数减1
- 计数为0时更换候选元素
时间复杂度 O(n)，空间复杂度 O(1)
*/
func majorityElement2(nums []int) int {
// 候选元素
candidate := nums[0]
// 计数器
counter := 1
// boyer-moore 投票
for i := 1; i < len(nums); i++ {
// 如果计数为0, 说明前面的元素都不同/元素相同， 更换候选元素
if counter == 0 {
candidate = nums[i]
}
if nums[i] == candidate {
counter++
} else {
counter--
}
}
return candidate
}