侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

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

Lin2J
2021-07-21 / 0 评论 / 0 点赞 / 115 阅读 / 945 字 / 正在检测是否收录...

剑指 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}$ ,如何找出这三个数字呢?

0

评论区