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.
因為眾數(shù)的出現(xiàn)次數(shù)大于二分之一彻采，所以排序后肯定在中間的位置独悴。
時間復雜度O(nlog n)，空間復雜度O(1)
代碼
int majorityElement(vector<int>& nums) {
if (nums.size() == 1) {
return nums[0];
}
sort(nums.begin(), nums.end());
int len=nums.size();
int mid=len/2;
if (len %2 != 0) {
return nums[mid];
}else {
if (nums[0] == nums[mid]){return nums[mid];}
else return nums[mid+1];
}
}
機智方法
class Solution {
public:
int majorityElement(vector<int>& nums) {
int major, counts = 0, n = nums.size();
for (int i = 0; i < n; i++) {
if (!counts) {
major = nums[i];
counts = 1;
}
else counts += (nums[i] == major) ? 1 : -1;
}
return major;
}
};
hash方法
出現(xiàn)次數(shù)大于n/2的數(shù)
class Solution {
public:
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];
}
};
隨機數(shù)方法
感覺這個有點看臉，如果一直落在非眾數(shù)上就很尷尬了
class Solution {
public:
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;
}
}
};
