【剑指Offer】（数组）数组中出现次数超过一半的数字（摩尔投票法）

约定不等于承诺〃 2022-03-16 12:48 152阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_e8a1b01a2df14cb2b228b30ee6a92163_tpId_13_tqId_11181_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

#### 解决方法 ####

二分查找

class Solution { 
    public:
        int MoreThanHalfNum_Solution(vector<int> numbers) { 
            if (numbers.size()==0) return 0;
            if (numbers.size()==1) return numbers[0];
            
            //摩尔投票法,核心思想是同加、异减 https://www.hijerry.cn/p/45987.html
            //每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个
            int score=0, res=numbers[0];
            for (int i=0;i<numbers.size();i++){ 
                if (numbers[i]==res) score++;
                else if (score==0) { res=numbers[i]; score=1;} //换人
                else score--;
            }
            //最后统计res是否出现超过了1/2
            int time=0;
            for (int i=0;i<numbers.size();i++)
                if (numbers[i]==res) time++;
            if (time>numbers.size()/2) return res;
            else return 0;
        
        }
    };

[https_www.nowcoder.com_practice_e8a1b01a2df14cb2b228b30ee6a92163_tpId_13_tqId_11181_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking