Last Updated on 2022-02-21 by Clay
題目
Given an arraynumsof sizen, return the majority element. The majority element is the element that appears more than⌊n / 2⌋times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3] Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2] Output: 2
Constraints:
n == nums.length1 <= n <= 5 * 104-231 <= nums[i] <= 231 - 1
Follow-up: Could you solve the problem in linear time and in O(1) space?
題目給定一組整數陣列的輸入，而我們要返回陣列中的多數元素（majority element）。
多數元素的定義是此元素在這陣列當中至少出現了超過一半的次數。
解題思路
這是個很好玩的題目，我一開始想出了兩種解答，但始終達成不了 Follow-up 所說的線性時間、O(1) 空間。
最後查看了他人的討論，這才發現使用 Moore voting algorithm（摩爾投票演算法）可以順利解開題目。
以下分別紀錄三種不同的解題方法。
排序法
由於多數元素一定佔超過一半長度的陣列，於是我們只需要先經過排序、再直接取陣列中間的值，就一定是多數元素。
排序法複雜度
由於使用了 quick sort，故時間複雜度一開始就是 n*log(n) 了。好處是不怎麼需要存取其他空間。
| Time Complexity | O(n*log(n)) |
| Space Complexity | O(1) |
排序法 C++ 範例程式碼
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size()/2];
}
};排序法 Python 範例程式碼
class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort()
return nums[len(nums)//2]Hash map
這題也可以很暴力地使用 hash map 來記錄每個元素出現的次數，這應該是很多人想到的第一感吧！
Hash map 複雜度
因為開了 O(n) 的 map，所以空間複雜度沒有達到 follow-up 的要求。
| Time Complexity | O(n) |
| Space Complexity | O(n) |
Hash map C++ 範例程式碼
class Solution {
public:
int majorityElement(vector<int>& nums) {
// Init
int major = 0;
unordered_map<int, int> mp;
// Count
for (auto n: nums) {
++mp[n];
if (mp[n] > nums.size()/2) {
major = n;
break;
}
}
return major;
}
};Hash map Python 範例程式碼
class Solution:
def majorityElement(self, nums: List[int]) -> int:
# Init
mp = dict()
# Count
for n in nums:
mp[n] = mp.get(n, 0) + 1
if mp[n] > len(nums)//2:
return nMoore voting algorithm（達成要求！）
基本上，這個演算法最早似乎是用來計算哪位候選人的投票數過半的。
我們先想像一個情境，設定一個當前正在接受檢驗的候選人，只要目前統計（count）為零，就先把檢驗的候選人設定成第一位計票者，接著在每次碰到相同的候選人時，將統計數（count）加一；反之碰到不同的候選人時，將統計票數（count）減一。
當然，我們所檢驗的第一位候選人可能並不是票數過半的那位，那麼這位候選人自然而然就會碰到比自己數量還多的候選人的票，自然計票（count）就會回歸到零。當我們又遇到計票數為零的時候，我們就會開始把下一位計票的候選人當成正在檢驗的候選人，開始重複上述的過程......
那最後留下來的候選人是誰呢？沒錯，就是票數過半的候選人才會留下來。
假設我們的投票分別是 A A C C B B B A A C C C，那麼我們計票的流程如下：
- [A] major = A, count = 1
- [A] major = A, count = 2
- [C] major = A, count = 1
- [C] major = A, count = 0
- [B] major = B, count = 1
- [B] major = B, count = 2
- [B] major = B, count = 3
- [A] major = B, count = 2
- [A] major = B, count = 1
- [C] major = B, count = 0
- [C] major = C, count = 1
- [C] major = C, count = 2
最後留下的只會是票數過半的 C。
Moore voting algorithm 複雜度
而這個演算法由於只需要存取當前計算的數值（major）跟計數（count），故空間複雜度是 O(1)。
而只需要把陣列跑一遍就統計完了，故為線性時間。
| Time Complexity | O(n) |
| Space Complexity | O(1) |
Moore voting algorithm C++ 範例程式碼
class Solution {
public:
int majorityElement(vector<int>& nums) {
// Init
int major = 0;
int count = 0;
// Count
for (auto n: nums) {
if (count == 0) major = n;
if (major == n) ++count;
else --count;
}
return major;
}
};Moore voting algorithm Python 範例程式碼
class Solution:
def majorityElement(self, nums: List[int]) -> int:
# Init
major = 0
count = 0
# Count
for n in nums:
if count == 0:
major = n
if major == n:
count += 1
else:
count -= 1
return major