學習路線/陣列與雜湊

169. 多數元素

Easy

Majority Element

ArrayHash TableSortingGreedyCounting

題目描述

給定一個大小為 n 的整數陣列 nums，找出其中的多數元素。多數元素是指出現次數大於 ⌊n/2⌋ 的元素，題目保證多數元素一定存在。

LeetCode 169原題連結 →

解法思路

  1. 使用 Boyer-Moore 投票演算法，維護一個候選人 candidate 和計數器 count
  2. 遍歷陣列：若 count 為 0，將當前元素設為候選人
  3. 若當前元素等於候選人則 count++，否則 count--
  4. 最終留下的候選人即為多數元素（因其出現次數超過一半）

複雜度分析

  • 時間複雜度：O(n)
  • 空間複雜度：O(1)

陣列 nums

2
[0]
2
[1]
1
[2]
1
[3]
1
[4]
2
[5]
2
[6]
候選人
?
計數
0
初始狀態：準備開始 Boyer-Moore 投票演算法。候選人尚未確定，計數為 0。
1 / 16