原题

LintCode 46. Majority Number

Description

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.

Notice

You may assume that the array is non-empty and the majority number always exist in the array.

Example

Given [1, 1, 1, 1, 2, 2, 2], return 1

解题

思路一

最简单的思路就是用Map统计每个数字出现的次数，然后取出现次数最多的数，即为答案。

class Solution {
public:
    /**
    * @param nums: A list of integers
    * @return: The majority number
    */
    int majorityNumber(vector<int> nums) {
        // write your code here
        map<int, int> m;
        auto vit = nums.begin();
        while (vit != nums.end()) {
            if (m.find(*vit) == m.end()) m[*vit] = 0;
            m[*vit]++;
            vit++;
        }
        auto mit = m.begin();
        int maxNum = 0;
        int maxCount = 0;
        while (mit != m.end()) {
            if (mit->second > maxCount) {
                maxCount = mit->second;
                maxNum = mit->first;
            }
            mit++;
        }
        return maxNum;
    }
};

思路二

如果要求空间复复杂度O(1)，可以用如下思路：
将每个数字理解为一个议案，那么每出现一次其实就是为这个议案的票数+1，如果出现其他议案，那么票数-1。当票数为0的时候，切换到下一个议案。
如果Majority Number一定存在，那么它的票数就一定不会被减到0，最后胜出。

class Solution {
public:
    /**
    * @param nums: A list of integers
    * @return: The majority number
    */
    int majorityNumber(vector<int> nums) {
        // write your code here
        int candidate, count = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (count == 0) {
                candidate = nums[i];
                count++;
            } else {
                if (candidate == nums[i])
                    count++;
                else
                    count--;
            }
        }
        return candidate;
    }
};