leetcode169. 多數元素
題目描述
給定一個大小為 n 的數組 nums ，返回其中的多數元素。多數元素是指在數組中出現次數 大于? n/2 ? 的元素。
你可以假設數組是非空的，并且給定的數組總是存在多數元素。
1.哈希
class Solution {
public:int majorityElement(vector<int>& nums) {int count = nums.size()/2; //獲取數組大小的一半unordered_map<int, int> hashTable; //<元素，元素出現的次數>for(int i = 0; i < nums.size(); i++){hashTable[nums[i]]++;if(hashTable[nums[i]] > count){return nums[i];}}return 0;}
};
hash代碼簡化版
class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map <int,int> mp;for(int n:nums) if(++ mp[n] > nums.size()/2) return n; return -1;}
};
2.Moore投票(最優解)
摩爾投票法，投我++，不投–，超過一半以上的人投我，那我穩贏哇
class Solution {
public:int majorityElement(vector<int>& nums) {int candidate = 0, votes = 0;for(int n : nums){if(votes == 0) candidate = n; if(n == candidate) ++votes;if(n != candidate) --votes;}return candidate;}
};
3.排序
class Solution {
public:int majorityElement(vector<int>& nums) {sort(nums.begin(), nums.end());return nums[nums.size() / 2]; //因為出現頻率大于n/2，所以排序后的中間位置必然是眾數}
};
4.位運算
class Solution {
public:int majorityElement(vector<int>& nums) {int res = 0;for(int i = 0 ; i < 32; ++i){int ones = 0;for(int n : nums)ones += (n >> i) & 1; //位運算法統計每個位置上1出現的次數，每次出現則ones+1res += (ones > nums.size()/2) << i; //如果1出現次數大于1/2數組的長度，1即為這個位置的目標數字}return res;}
};
＞)
