leetcode 169.Majority Element

这道题虽然简单，但适合用来练习各种解法。《剑指offer》5.2节 面试题29与此题一样，并且给出了leetcode官方题解未给出的快速选择的解法。

用哈希表解决

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int,int> count;int majority = 0;int cnt = 0;for(auto num:nums){count[num]++;if(count[num] > cnt){cnt = count[num];majority = num;}}return majority;}
};

先排序再取nums[n/2]

class Solution {
public:int majorityElement(vector<int>& nums) {int len = nums.size();srand(time(0));quick_sort(nums,0,len-1);return nums[len/2];}int partition(vector<int>& nums,int left,int right){if(left >= right)return left;int random = rand()%(right - left +1);swap(nums[left],nums[left + random]);int pivot = nums[left];while(left < right){while(left<right && pivot < nums[right]) right--;nums[left] = nums[right];  while(left<right && nums[left]<=pivot) left++;nums[right] = nums[left];}nums[left] = pivot;return left;}void quick_sort(vector<int>& nums,int left,int right){if(left>=right) return;int pivot_pos = partition(nums,left,right);quick_sort(nums,left,pivot_pos-1);quick_sort(nums,pivot_pos+1,right);}
};

随机化方法

class Solution {
public:int majorityElement(vector<int>& nums) {srand(0);int len = nums.size();int random = 0; int cnt = 0;while(true){random = rand()%len;cnt = 0;for(auto num:nums){if(num == nums[random]){cnt++;if(cnt >len/2)return num;}}}}
};

Boyer-Moore投票法

《剑指offer》5.2节也给出了这种解法

class Solution {
public:int majorityElement(vector<int>& nums) {int candidate = nums[0];int count = 1;for(int i = 1;i < nums.size();i++){if(nums[i] == candidate){count++;}else{count--;if(count == 0){candidate = nums[i];count = 1;}}}return candidate;}
};