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

---

题目描述

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

解题思路

要找的元素的出现次数是超过数组一半的，也就是说与该元素相同的值占据数组的一半之多。面对这种要求可以采用阵地攻守思想。真正守下阵地，并占据数组个数多于数组长度一半的元素，称为兵王。

• 数组第一个元素作为第一个士兵，守阵地，此时这个小分队的成员人数count=1；
• 当遇到相同元素时，小分队人数 +1 count++；
• 当遇到不同的元素时，同归于尽，小分队人数 -1 count–；
• 当小分队人数为 0 时，换下一个元素组成新的小分队守护阵地，若上叙步骤进行。
• 当遍历完整个数组，当小分队中还有人在时，说明这个元素有可能是要找的。
• 再遍历整个数组，记录数组中这个元素的个数是否大于数组长度的一半。

代码

class Solution
{
public:
    int MoreThanHalfNum_Solution(vector<int> numbers)
    {
        if (numbers.empty())
            return 0;
        int length = numbers.size();
        int times = 1, result = numbers[0];
        // 找到最后坚守阵地的士兵
        for (int i=1; i<length; i++)
        {
            if (times==0) // 小分队全部牺牲，将当前元素作为新的小分队成员
            {
                result = numbers[i];
                times = 1;
            }
            else if (numbers[i] == result) // 遇到相同的士兵，加入小分队
                times++;
            else // 遇到的是不同的敌人，同归于尽
                times--;
        }
        // 判断最后坚守的士兵（元素），是否为真正要寻找的兵王
        times = 0;
        for (int i=0; i<length; i++)
        {
            if (numbers[i] == result)
                times++;
        }
        return (times>(length/2) ? result : 0);
    }
};

---

参考博文链接：https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163?f=discussion

https://cuijiahua.com/blog/2017/12/basis_28.html