Description
給定大小為
n的陣列nums，回傳多數元素。多數元素是出現次數超過n/2的元素。保證多數元素一定存在。
Example:
Input: nums = [2,2,1,1,1,2,2] Output: 2
Intuition#
核心思路：Boyer-Moore 投票演算法——把多數元素看作「票數最多的候選人」，用 +1/-1 計票。
- 因為多數元素超過 n/2 次，其他所有元素加起來也不足以「抵銷」它
- 維護候選人和計數器，相同 +1、不同 -1，歸零時換候選人
Approaches#
1: HashMap 計數#
- 概念: 用 HashMap 統計每個元素的出現次數，找出超過 n/2 的
- 時間複雜度:
O(n)- 遍歷一次 - 空間複雜度:
O(n)- HashMap 儲存
class Solution {
fun majorityElement(nums: IntArray): Int {
val count = HashMap<Int, Int>()
for (num in nums) {
count[num] = (count[num] ?: 0) + 1
if (count[num]!! > nums.size / 2) return num
}
throw IllegalArgumentException()
}
}⭐2: Boyer-Moore Voting Algorithm#
- 概念: 維護候選人
candidate和計數器count，遇到相同元素 +1，不同 -1，歸零時更換候選人 - 時間複雜度:
O(n)- 一次遍歷 - 空間複雜度:
O(1)- 只用兩個變數
class Solution {
fun majorityElement(nums: IntArray): Int {
var candidate = nums[0]
var count = 0
for (num in nums) {
if (count == 0) candidate = num
count += if (num == candidate) 1 else -1
}
return candidate
}
}補充：排序法
排序後，多數元素一定出現在中間位置 nums[n/2]。
class Solution {
fun majorityElement(nums: IntArray): Int {
nums.sort()
return nums[nums.size / 2]
}
}時間 O(n log n)，空間 O(1)（原地排序）。
🔑 Takeaways#
- Pattern: Boyer-Moore Voting 是找多數元素的經典 O(1) 空間演算法
- 關鍵技巧: 核心直覺是「多數元素的票數永遠不會被完全抵銷」；此演算法可推廣到出現超過 n/3 次的元素（LC 229）