题解 | #数组中出现次数超过一半的数字#

//https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&&tqId=11181&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
//JZ39 数组中出现次数超过一半的数字
//遍历把两个不同的数删去，最后剩下的就是众数
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        //      sort(numbers.begin(), numbers.end());
        //      int ans = numbers[numbers.size() / 2];
        //      return ans;

        int ans = 0;
        int count = 0; //count计数

        for (int i = 0; i < numbers.size(); ++i) {
            if (count == 0) { //如果count为 0，把ans换成当前的数继续遍历
                ans = numbers[i];
                ++count;
            }
            else {
                ans == numbers[i] ? count++ : count--; //如果两个数相同就--count，不相同就++count
                //比如说当前ans是4，count是1，下一个数也是4，那么count就会是2，那么要再遍历两个不同于4的数从才把ans换成别的数
            }
        }

        return ans;
    }
};