majority-element

Majority Element – LeetCode 169

Problem

Description

Given an array of size n, find the majority element. The majority element is the element that appears more than n/2 times.

Answer

Original

Code

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[nums.size() / 2];
    }
};

思路

巧妙的排序直接得到答案，收益于C++的STL对sort的实现，时间复杂度$O(nlog(n))$，空间复杂度$O(1)$。
耗时$25$ ms，排名$73.47\%$

Better

思路

由于重复频率超过 floor(n/2)的数字只有一个，等价于与其余数字出现频率的差大于零。这个算法有名字：Boyer–Moore majority vote algorithm，时间复杂度$O(n)$，空间复杂度$O(1)$。
官方解中有更多解答
耗时$19$ ms，排名$46.2\%$

Code

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