问题描述
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.
解题思路
类似于堆栈，若当前元素与majority元素相等时，计数器count加1，若不等，则计数器减一。当计数器减为零时，更换majority元素。下边给出多种解法
int majorityElement(vector<int>& nums) {
int max = nums[0];
int count = 1 ;
for(int i = 0; i<nums.size();i++){
if(nums[i]==max){
count++;
}else{
count--;
if(count <1){
max = nums[i];
count++;
}
}
}
return max;
}
Hash Table
int majorityElement(vector<int>& nums) {
unordered_map<int, int> counts;
int n = nums.size();
for (int i = 0; i < n; i++)
if (++counts[nums[i]] > n / 2)
return nums[i];
}
sort
因为majority的出现次数超过n/2次，所以当nums排好序后，位于中间的元素即为所求元素
int majorityElement(vector<int>& nums) {
nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
return nums[nums.size() / 2];
}
Randomization
随机化，有着很好的运行速度
int majorityElement(vector<int>& nums) {
int n = nums.size();
srand(unsigned(time(NULL)));
while (true) {
int idx = rand() % n;
int candidate = nums[idx];
int counts = 0;
for (int i = 0; i < n; i++)
if (nums[i] == candidate)
counts++;
if (counts > n / 2) return candidate;
}
}
