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

Lin2J
2021-07-21 / 0 评论 / 88 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。

解题思路:

如果一定存在次数超过一半的数字,那么将数组中每两个不同的数对相互抵消,最后留下来的一定是超过一半次数的数字。

如果没有指明一定存在该数字,那么需要对最终结果进行验证,计算其出现的次数超过总数的一半。

代码:

public int majorityElement(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int ans = nums[0];
    int times = 1;
    for (int i = 1; i < nums.length; i++) {
        if (times == 0) {
            ans = nums[i];
            times++;
        } else {
            if (ans == nums[i]) {
                times++;
            } else {
                times--;
            }
        }
    }
    return ans;
}

复杂度分析

  • 时间复杂度$O(N)$:$N$ 为数组的元素个数。需要对每个元素进行遍历比较,比较占用 $O(1)$ 的时间。
  • 空间复杂度$O(1)$anstimes 都是占用常数大小的额外空间。

思考:如果是存在三个数字,它们出现的总次数占用了总数的 $\frac{1}{4}$ ,如何找出这三个数字呢?