Majority Element

LeetCode

第45天。

今天的题目是Majority Element:

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.

最简单的想法就是，遍历一遍序列，记录出现的次数，然后在遍历一遍刚才记录的次数，如果大于k就直接返回，这种时候一般会用到hash table，在c++中就是unordered_map:

1
2
3
4
5
6
7
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;
}

这种方法的时间复杂度是O(n),空间复杂度也是O(n).

虽然很简单，但是这道题目在dicuss中也有很多有趣的解法:

  • 因为Majority Element在序列中存在n/2个，所以假如这个序列时有序的话，他一定会出现在中间:
1
2
3
4
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
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，这个方法的正确性我也不是很确定:
1
2
3
4
5
6
7
8
9
10
11
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;
}