描述

题目描述

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

要求：空间复杂度：O(1)，时间复杂度 O(n)

输入描述：

保证数组输入非空，且保证有解

示例

输入：
[1,2,3,2,2,2,5,4,2]
返回值：2

知识点：数组 难度：⭐⭐

题解

图解

方法一：抵消计数

解题思路：

思路其实是简单的抵消 + 计数，对于当前元素与前一个元素数值不同，则进行抵消和计数，最后剩下的数一定是超过一半的那个数字，因为那个数字抵消完其他数字，最后至少剩下一个

算法流程：

• 一个变量保存数组中 [0…i] 元素中数量最大的那个数，另一个变量保存这个数在 [0…i] 元素中与其他元素抵消后的数量
• 遍历每一个元素，对于连续相同的数字，记录改元素的数量
• 与前一个数不相同，则计数减少，直到为0
  • 如果计数为0，则更新res和count，即重新计算目标值的出现次数
• 最后留下的值一定是超过一般的数字

Java 版本代码如下：

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int res = array[0], count = 1;
        for(int i = 1; i < array.length; i++) {
            // 对于连续相同的数字，记录改元素的数量
            if(array[i] == res) {
                count++;
            } else {
                // 与前一个数不相同，则计数减少，直到为0
                count--;
                // 更新res和count，即重新计算目标值的出现次数
                if(count == 0) {
                    res = array[i];
                    count = 1;
                }
            }
        }
        // 最后留下的值一定是超过一般的数字
        return res;
    }
}

复杂度分析：

时间复杂度 $O(N)O(N)$：需要遍历每个元素

空间复杂度 $O(1)O(1)$：只用到两个整型变量

方法二：排序后的中间数

解题思路：

其实通过找规律，或者说按照常理来讲，超过一半的数，那个数一定会在中间位置，比如极端的例子：11122

算法流程：

• 先排序
• 数组中间位置的元素就是元素数量超过一半的那个数

Java 版本代码如下：

import java.util.Arrays;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        Arrays.sort(array);
        return array[array.length >> 1];
    }
}

复杂度分析：

**时间复杂度 **：$O(NlogN)O(NlogN)$，排序需要的时间

**空间复杂度 **：$O(1)O(1)$，不需要额外空间