题目大意：给你一个数组，其中一个数出现超过n/2次，问你出现次数最多的那个数是什么？
Problem:
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Ideas:
Solution 1:
Hash table O(n) / O(n)
|
|
// Author: Huahua // Runtime : 23 ms class Solution { public: int majorityElement(vector<int>& nums) { unordered_map<int, int> count; const int n = nums.size(); for (const int num : nums) if (++count[num] > n / 2) return num; return -1; } }; |
Solution 2:
BST O(nlogk) / O(n)
|
|
// Author: Huahua // Runtime : 19 ms class Solution { public: int majorityElement(vector<int>& nums) { map<int, int> count; const int n = nums.size(); for (const int num : nums) if (++count[num] > n / 2) return num; return -1; } }; |
Solution 3:
Randomization O(n) / O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Runtime: 19 ms class Solution { public: int majorityElement(vector<int>& nums) { srand(time(nullptr)); const int n = nums.size(); while (true) { const int index = rand() % n; const int majority = nums[index]; int count = 0; for (const int num : nums) if (num == majority && ++count > n/2) return num; } return -1; } }; |
Solution 4:
Bit voting O(n) / O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: int majorityElement(vector<int>& nums) { const int n = nums.size(); int majority = 0; for (int i = 0; i < 32; ++i) { int mask = 1 << i; int count = 0; for (const int num : nums) if ((num & mask) && (++count > n /2)) { majority |= mask; break; } } return majority; } }; |
Solution 5:
Moore Voting O(n) / O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: int majorityElement(vector<int>& nums) { int majority = nums.front(); int count = 0; for (const int num : nums) { if (num == majority) ++count; else if (--count == 0) { count = 1; majority = num; } } return majority; } }; |
Solution 6:
Full sorting O(nlogn) / O(1)
|
|
class Solution { public: int majorityElement(vector<int>& nums) { std::sort(nums.begin(), nums.end()); return nums[nums.size()/2]; } }; |
Solution 7:
Partial sorting O(n) / O(1)
|
|
class Solution { public: int majorityElement(vector<int>& nums) { nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end()); return nums[nums.size() / 2]; } }; |
Solution 8:
Divide and conquer O(nlogn) / O(logn)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: int majorityElement(vector<int>& nums) { return majorityElement(nums, 0, nums.size() - 1); } private: int majorityElement(const vector<int>& nums, int l, int r) { if (l == r) return nums[l]; const int m = l + (r - l) / 2; const int ml = majorityElement(nums, l, m); const int mr = majorityElement(nums, m + 1, r); if (ml == mr) return ml; return count(nums.begin() + l, nums.begin() + r + 1, ml) > count(nums.begin() + l, nums.begin() + r + 1, mr) ? ml : mr; } }; |
Divide and conquer O(nlogn) / O(logn)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public: int majorityElement(vector<int>& nums) { return majorityElement(nums, 0, nums.size() - 1).first; } private: pair<int, int> majorityElement(const vector<int>& nums, int l, int r) { if (l == r) return {nums[l], 1}; int mid = l + (r - l) / 2; auto ml = majorityElement(nums, l, mid); auto mr = majorityElement(nums, mid + 1, r); if (ml.first == mr.first) return { ml.first, ml.second + mr.second }; if (ml.second > mr.second) return { ml.first, ml.second + count(nums.begin() + mid + 1, nums.begin() + r + 1, ml.first) }; else return { mr.first, mr.second + count(nums.begin() + l, nums.begin() + mid + 1, mr.first) }; } }; |
