# Majority Element

Nov 10, 2017

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.

int majorityElement(vector<int>& nums) {
int size = nums.size();
int k = size/2;
unordered_map<int,int> map;
for(auto i:nums) map[i]++;
for(auto p:map) if (p.second > k) return p.first;
}


• 因为Majority Element在序列中存在n/2个，所以假如这个序列时有序的话，他一定会出现在中间:
int majorityElement(vector<int>& nums) {
nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
return nums[nums.size() / 2];
}


nice的学到了一个新的函数。

• 同样是因为出现了k/2次，所以我们如果随机选取一个元素的话，有一半的概率可以直接选到Majority Element:
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;
}
}

• Moore Voting Algorithm，这个方法的正确性我也不是很确定:
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;
}

LeetCodeLeetCode

Maximum Depth of Binary Tree

Move-Zeroes