LeetCode169 - (easy) Majority Element

1
2

Input: [3,2,3]
Output: 3

1
2

Input: [2,2,1,1,1,2,2]
Output: 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// Runtime: 44 ms, faster than 62.77% of C++ online submissions for Majority Element.
// Memory Usage: 19.8 MB, less than 6.06% of C++ online submissions for Majority Element.
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> count;
        const int n=nums.size();
        for(const int num:nums)
            //递增哈希表中的计数并判断
            if (++count[num]>n/2)
                return num;
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// Runtime: 44 ms, faster than 62.77% of C++ online submissions for Majority Element.
// Memory Usage: 19.7 MB, less than 6.06% of C++ online submissions for Majority Element.
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int,int> count;
        const int n=nums.size();
        for(const int num:nums)
            if (++count[num]>n/2)
                return num;
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// Runtime: 40 ms, faster than 75.16% of C++ online submissions for Majority Element.
// Memory Usage: 19.7 MB, less than 6.06% of C++ online submissions for Majority Element.
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //初始化种子
        srand(time(nullptr));
        const int n=nums.size();
        while(true){
            //取随机数的索引
            const int index=rand()%n;
            const int maj=nums[index];
            int cnt=0;
            for(const int num:nums)
                //当遍历到取的这个数时，计数增加并继续判断是否为majority
                if(num==maj && ++cnt>n/2)
                    return num;
        }
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// Runtime: 68 ms, faster than 14.31% of C++ online submissions for Majority Element.
// Memory Usage: 19.7 MB, less than 6.06% of C++ online submissions for Majority Element.
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        const int n=nums.size();
        int result=0;
        //对每一位遍历
        for(int i=0;i<32;++i){
            //当前位的mask
            int mask=1<<i;
            int cnt=0;
            for(const int num:nums)
                //对当前位的1计数
                if(num&mask)
                    ++cnt;
            //若当前位的1多于32个，则结果中当前位一定是1
            if(cnt>n/2)
                result|=mask;
        }
        return result;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Runtime: 32 ms, faster than 87.31% of C++ online submissions for Majority Element.
// Memory Usage: 19.7 MB, less than 6.06% of C++ online submissions for Majority Element.
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //初始化假设值和计数值
        int hyp=nums[0];
        int cnt=0;
        for(const int num:nums){
            //若当前值等于假设值则计数增加
            if(num==hyp)
                ++cnt;
            //若当前值不等于假设值则计数减少，并判断是否减为0
            else if(--cnt==0){
                //减到0时更新假设值和计数值
                hyp=num;
                cnt=1;
            }
        }
        return hyp;
    }
};

1
2
3
4
5
6
7
8
9

// Runtime: 72 ms, faster than 11.92% of C++ online submissions for Majority Element.
// Memory Usage: 19.6 MB, less than 6.06% of C++ online submissions for Majority Element.
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};

1
2
3
4
5
6
7
8
9

// Runtime: 40 ms, faster than 75.16% of C++ online submissions for Majority Element.
// Memory Usage: 19.8 MB, less than 6.06% of C++ online submissions for Majority Element.
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        nth_element(nums.begin(),nums.begin()+nums.size()/2,nums.end());
        return nums[nums.size()/2];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// Runtime: 44 ms, faster than 62.77% of C++ online submissions for Majority Element.
// Memory Usage: 19.6 MB, less than 6.06% of C++ online submissions for Majority Element.
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        return majorityElement(nums,0,nums.size()-1).first;
    }
    //递归函数，返回pair表示众数及其出现次数
    pair<int,int> majorityElement(const vector<int> &nums,int l,int r){
        //递归终点
        if(l==r) 
            return {nums[l],1};
        //取中点分治
        int mid=(l+r)/2;
        auto rl=majorityElement(nums,l,mid);
        auto rr=majorityElement(nums,mid+1,r);
        //左右两侧众数相等，直接返回众数和频率
        if(rl.first==rr.first)
            return {rl.first,rl.second+rr.second};
        //左右两侧众数不相等，对两个众数的频率讨论
        if(rl.second>rr.second)
            //若左侧众数频率大，则结果是左侧众数，其出现的频率是左侧的频率（已求出）加右侧的频率（用count统计）
            return {rl.first,rl.second+count(nums.begin()+mid+1,nums.begin()+r+1,rl.first)};
        else
            return {rr.first,rr.second+count(nums.begin()+l,nums.begin()+mid+1,rr.first)};
    }
};