描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

1<=数组长度<=50000，0<=数组元素<=10000

示例1

输入：
[1,2,3,2,2,2,5,4,2]

返回值：
2

示例2

输入：
[3,3,3,3,2,2,2]

返回值：
3

示例3

输入：
[1]

返回值：
1

思路

这道题是让找出数组中数量最多的数，最直观的解法就是将数组排好序，然后取中位数即可。但是这么做并不是最优解，接下来有一种办法能在O(n)的时间复杂度内解决这道题。

1. 定义一个计数器count；用于存储结果的 res。count 用来标识这个字符串是否是超过一半的那个字符串；res 用来存储最终结果。
2. 咱们开始遍历数组，当 count = 0时，说明前面并没有找到出现次数最多的那个字符串，那么就把当下的字符串 str 暂定为最终的结果，count = 1；res = str。
3. res 和 遍历到的 str 字符串不相等时，看看 count 是否大于 0，如果大于 0 ，则说明 res 是前面出现次数最多的那个字符串，当前的 str 抵消一次 count， count --；
4. res 和 遍历到的 str 字符串相等时，说明前面 str 和前面出现次数最多的字符串一致，count ++。

AC 代码

    public int MoreThanHalfNum_Solution(int [] array) {
        int count = 0;
        int res = 0;
        for (int x : array) {
            // 等于 0，说明前面没有找到数量最多的数，从新开始计数
            if (count == 0) {
                res = x;
                count ++;
            } else if (res == x) {
                // 相等时，累加即可
                count ++;

            } else {
                // 不相等时，先判断前面是否选出数量最多的数，选出来就 --
                if (count > 0) {
                    count --;
                } else {
                    // 没有选出来酒用当下的数
                    res = x;
                }
            }
        }
        // 返回最终结果
        return res;
    }

• 时间复杂度：O(n)，n 为数组长度。
• 空间复杂度：O(1)。

最后

大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。