Majority Element

leetcode bit-opearaion map sort majority

原题链接

题意

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.

解法

• 哈希表: 思路也比较清晰，就是通过哈希表来存储,
  然后再查找哈希表中出现最多的元素, 代码略.

• 位运算: 这个方法是看了Solution之后才知道的,
  这里假设数据值范围为(1，2^32-1),
  那么我们需要一个32个元素的list,初始值都为0.
  这里的32表示元素转换成二进制之后的32位数.
  对于每一位数, 遍历数据list里的所有数,记录该位为1的个数.
  如果个数>=len(num)/2+1, 则该位为1, 否则为0,
  同理算出每一位，再转换成10进制数即为出现次数最多的数.

• 随机采样算法：因为题目中告诉了这个数一定会出现，而且出现的次数>=1/2,
  那么我们可以随机取一个数进行判断.理论上平均两次就可以找到这个数.
  当然从算法的角度上来看这个算法的最坏情况是infinite(考虑永远都取不到正确数的情况),
  但对于一个实际问题这个方法还是可行的.

• moore’s voting 算法：这个算法以前没有听说过，是专门解决这一问题的，给一个链接让大家参考一下
  http://http://www.cs.utexas.edu/~moore/best-ideas/mjrty/

• 具体看代码

code

 class Solution {
public:
    // 41 ms
    int majorityElement(vector<int> &num) {
        const int bitCount = 32;
        const int zero = 0;
        vector<int> bitRes(bitCount, zero);
        for(int i = 0; i < num.size(); i++) {
            for(int j = 0; j < bitCount; j++) {
                if(num[i] & (1 << j)) {
                    bitRes[j]++;
                }
            }
        }
        int candidate = 0;
        const int baseLen = num.size() / 2;
        for(int i = 0; i < bitCount; i++) {
            // 如果个数>=len(num)/2+1, 则该位为1, 否则为0
            if(bitRes[i] > baseLen) {
                candidate += (1 << i);
            }
        }
        return candidate;
    }
    // O(N·logN): time
    // 46 ms
    int majorityElement2(vector<int> &num) {
        sort(num.begin(), num.end());
        return num[num.size() / 2];
    }
    // O(n): time, O(1): space
    // 27 ms
    // see: http://stackoverflow.com/questions/3740371/finding-the-max-repeated-element-in-an-array
    int majorityElement3(vector<int> &num) {
        int k = 0;
        int res;
        for(int i = 0; i < num.size(); i++) {
            if(k == 0) {
                res = num[i];
                k = 1;
            } else {
                if(res == num[i]) {
                    k++;
                } else {
                    k--;
                }
            }
        }
        return res;
    }
    // O(N'·logN' + O(N')): time, where N' is the number of unique elements of array num
    // 48 ms
    // O(N'): space
    int majorityElement4(vector<int> &num) {
        map<int, int> res;
        for(int i = 0; i < num.size(); i++) {
            res[num[i]]++;
        }
        int maxIdx = 0;
        int candidate;
        for(map<int, int>::iterator it = res.begin(); it != res.end(); it++) {
            if(maxIdx < it->second) {
                maxIdx = it->second;
                candidate = it->first;
            }
            /* or
                if(it->second > num.size() / 2) return it->first;
            */
        }
        return candidate;
    }
};