描述

题目描述

给一个长度为 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

知识点:数组 难度:⭐⭐


题解

图解

image-20211025140328472

方法一:抵消计数

解题思路:

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

算法流程:
  • 一个变量保存数组中 [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),不需要额外空间