NC73数组中出现次数超过一半的数字

NC73数组中出现次数超过一半的数字

- 1、题目描述：

- 2、题目链接：
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=117&tqId=37770&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

-3、 设计思想：

详细操作流程看下图：

-5、代码：
c++版本:

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int cnt = 0;//票数
        int res = 0;//最终返回的结果
        for(int i = 0;i < numbers.size();i ++){
            if (cnt == 0) res = numbers[i];//如果票数为0就更新出现次数多的那个
            cnt += ((numbers[i] == res)? 1 : -1);
        }
        cnt = 0;
        for(int i = 0;i < numbers.size();i ++){//检查res出现的次是否超过了数组长度的一半
            if(res == numbers[i]) cnt ++;
            if(cnt > (numbers.size()/2)) return res;
        }
        return 0;
    }