leetcode 169: majority element

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.

vote algorithm: 维持一个pair, 代表当前元素和投票数，每次往后移，对该投票数进行增减，最后剩下的那个pair 的值就是marjority number. 

class Solution {

public:

    int majorityElement(vector<int>& nums) {

        //sanity check

        if (nums.size() == 0) return -1;

        pair<int, int> np;

        np = make_pair(nums[0],1);

        for (int i = 1; i < nums.size(); i++) {

            if (nums[i] == np.first) np.second++;

            else np.second--;

            if (np.second == 0) np = make_pair(nums[i], 1);

        }

        return np.first;

    }

};

majority element II

Given an integer array of size n, find all elements that appear more than n/3

这个题目也是利用上面的vote algorithm 来解，区别是上面的majority element是求众数，结果只有一个数，但是这个题目是找> n/3， 结果最多是2个数，也可能没有数， 相对于上题使用一个变量来记录，这个题目需要用到两个变量来记录，这两个变量分别取两个不同的在input里面的值，如果检测到元素与其值相等，counter++， 如果counter是0， 那么就把这个值给这个变量，如果不相等,counter--，这样下来是5种情况，最后得到的是两个candidates， 并不是直接就是答案，我们需要再遍历一遍Input，记录这两个元素出现次数，如果> n/3， 就加入到结果集合中。

class Solution {

public:

    vector<int> majorityElement(vector<int>& nums) {

        vector<int> rst;

        if (nums.size() == 0) return rst;

        pair<int, int> ma1 = make_pair(0,0);

        pair<int, int> ma2 = make_pair(0,0);

        for (int i = 0; i < nums.size(); i++) {

            if (ma1.second != 0 && ma1.first == nums[i]) {

                ma1.second++;

            } else if (ma2.second != 0 && ma2.first == nums[i]) {

                ma2.second++;

            } else if (ma1.second == 0) {

                ma1.first = nums[i];

                ma1.second++;

            } else if (ma2.second == 0) {

                ma2.first = nums[i];

                ma2.second++;

            } else {

                ma1.second--;

                ma2.second--;

            }

        }

        int count1 = 0;

        int count2 = 0;

        for (int i : nums) {

            if (i == ma1.first ) count1++;

            else if (i == ma2.first) count2++;

        }

        if (count1 > nums.size()/3) rst.push_back(ma1.first);

        if (count2 > nums.size()/3) rst.push_back(ma2.first);

        return rst;

    }

};