Majority Number

Posted on   |   In   |  

求出数组中数量超过一半的数

Majority Number

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.
题目大意:给定一个数组，求出出现次数超过一半的元素。(假设数组不为空，并且这个元素一定存在)

  • 解决这种问题最常见的方式就是建立hash（二叉搜索树）来保存相应的数字出现的频率，进而统计出超过一半的数。这回消耗额外的O(n)的空间，时间为O(n)。
  • 还有的方法就是对数组进行排序，因为有一个数的数量超过了⌊ n/2 ⌋,所以这个数一定会出现在n/2的位置。排序的O(nlogn)
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if(nums.empty()) return 0;
        sort(nums.begin(), nums.end());
        
        return nums[(nums.size() -1)/2];
    }
};

  • 位操作，选出int的所有位中的超过半数的数(1或0)，这32位组成的数字一定是最后所求

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int ret = 0, majority = nums.size()/2;
            
            for(int i = 31; i>=0; i--){
                int count = 0;
                for(int n:nums){
                    if(n & (1<<i))
                        count++;
                }
                count = count>majority?1:0;
                ret |= count<<i;
            }
            return ret;
        }
    };

  • 这里介绍一种更加优雅的方法，只消耗O(1)的空间。Boyer-Moore Majority Vote algorithm,在数组中找到两个不相同的元素并删除它们，不断重复此过程，直到数组中元素都相同，那么剩下的元素就是主要元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        
        int val = nums[0];
        int copies = 0;
        
        for(int i = 0; i < nums.size(); i++){
            if(copies == 0)
                val = nums[i];
            
            if(nums[i] == val)
                copies++;
            else
                copies--;
        }
        return val;
    }
};

Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
题目变了，求出超出总数量1/3的元素。注意可能有两个元素了。特别需要注意的是:一定要注意不能让这两个数重复了，去重，去重，去重,实际上选定两个数，选出两个数的数量之和超过2/3.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
         vector<int> res;
        int m = 0, n = 0, cm = 0, cn = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] == m){
                cm++;
            }
            else if (nums[i] == n){
                cn++;
            }
            else if (cm == 0){
                m = nums[i];
                cm = 1;
            }
            else if (cn == 0){
                n = nums[i];
                cn = 1;
            }
            else{
                --cm;
                --cn;
            }
        }
        
        cm = cn = 0;
        for (auto& a : nums)
        {
            if (a == m){
                cm++;
            }
            else if (a== n){
                cn++;
            }
        }
        if (cm > nums.size() / 3){
            res.push_back(m);
        }
        if (cn > nums.size() / 3){
            res.push_back(n);
        }

        return res;
    }
};

给出一种错误的思路：测试用例为[3, 3, 4],求出来的是[],但正确的答案却是[3],想了想，是因为在给出两个候选数的时候，没有去重
数组第一个元素3:
num1 = 3;
数组第二个元素3:
这时候由于count == 0,会导致将3赋给num2，从而重复
数组第三个元素4:
与两个数都不相同，导致均减一，现在统计的数目都为0

同样滴:测试用例[1,2,2,3,2,1,1,3]
最后返回的数字为:num1 = 1, count1 = 1; num2 = 3, count2 = 3;

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
28
29
30
31
32
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> ret;
        int num1 = 0, num2 = 1;
        int count1 = 0, count2 = 0;
        
        for(int i = 0; i< nums.size(); i++){
            if(count1 == 0) num1 = nums[i];
            else if(count2 == 0)    num2 = nums[i];
            
            else if(nums[i] == num1) count1++;
            else if(nums[i] == num2) count2++;
            
            else{
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == num1) count1++;
            else if(nums[i] == num2) count2++;
        }
        if(count1 > nums.size()/3) ret.push_back(num1);
        if(count2 > nums.size()/3) ret.push_back(num2);
        return ret;
    }
};

参阅:http://www.jianshu.com/p/dfd676b71ef0