算法的学习笔记—数组中出现次数超过一半的数字(牛客JZ39)

举报
尘觉 发表于 2024/08/26 19:01:54 2024/08/26
【摘要】 在算法和数据结构领域,找到数组中出现次数超过一半的数字是一个经典问题。这种问题在实际应用中也有广泛的使用场景,例如投票系统、数据分析等。今天,我们将探讨一种高效的解决方法——Boyer-Moore多数投票算法。

😀前言
在算法和数据结构领域,找到数组中出现次数超过一半的数字是一个经典问题。这种问题在实际应用中也有广泛的使用场景,例如投票系统、数据分析等。今天,我们将探讨一种高效的解决方法——Boyer-Moore多数投票算法

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

NowCoder

问题描述

给定一个长度为 n 的数组,要求找到其中一个数字,其出现次数超过了数组长度的一半。简单来说,这个数字的出现次数超过了 n/2。例如:

  • 输入:[1, 2, 3, 2, 2, 2, 5, 4, 2]
  • 输出:2

在这个例子中,数字 2 出现了5次,超过了数组长度的一半,因此返回 2

约束条件

  • 数据范围:数组长度 n ≤ 50000,数组中元素的值在 0 ≤ val ≤ 10000 之间。
  • 时间复杂度要求:O(n)
  • 空间复杂度要求:O(1)

😄示例

示例1

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

示例2

输入:[3,3,3,3,2,2,2]
返回值:3

示例3

输入:[1]
返回值:1

🥰解题思路

这个问题是典型的多数投票问题,可以利用 Boyer-Moore Majority Vote Algorithm 来解决,从而将时间复杂度优化为 O(N)。

Boyer-Moore 多数投票算法

算法的核心思想是通过一次遍历数组,动态维护一个候选多数元素,并利用计数器 cnt 来统计该元素的“有效”出现次数。具体步骤如下:

  1. 计数初始化:设定一个计数器 cnt 和一个候选多数元素 majority。初始时将数组的第一个元素设为候选元素,cnt 设为 1。
  2. 遍历数组
    • 对于数组中的每个元素,判断它是否与当前的候选元素相等:
      • 如果相等,则将 cnt 加 1。
      • 如果不相等,则将 cnt 减 1。
    • cnt 减至 0 时,意味着当前的候选元素在已遍历的部分中不再是多数,此时需要重新设定候选元素为当前元素,并将 cnt 重置为 1。
  3. 验证候选元素:在遍历完成后,得到的候选元素未必一定是数组中的多数元素,因此需要进行一次验证。统计候选元素在数组中出现的总次数,如果其次数超过数组长度的一半,则它就是我们要找的多数元素。

算法的正确性分析

  • 如果前 i 个元素已经遍历完毕且 cnt == 0,这表示当前数组前 i 个元素没有多数元素,或者有但其出现次数小于 i/2。在这种情况下,剩余的 n - i 个元素中,如果多数元素确实存在,其数量仍然会超过 (n - i) / 2,因此通过继续遍历,最终可以找出这个多数元素。
  • 在最坏的情况下,算法需要遍历两次数组:第一次找出候选元素,第二次验证其是否为多数元素。因此,总的时间复杂度为 O(N)。

通过这种方法,我们能够在 O(N) 的时间复杂度和 O(1) 的空间复杂度下,找到数组中出现次数超过一半的数字。

😊代码实现

下面是基于上述思路的 Java 代码实现:

public int MoreThanHalfNum_Solution(int[] nums) {
    // 第一步:初始化候选元素为数组的第一个元素,计数器 cnt 初始值为 1
    int majority = nums[0];
    int cnt = 1;

    // 第二步:遍历数组,寻找可能的多数元素
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == majority) {
            // 如果当前元素和候选元素相同,计数器加 1
            cnt++;
        } else {
            // 如果当前元素和候选元素不同,计数器减 1
            cnt--;
            // 当计数器为 0 时,更新候选元素为当前元素,并将计数器重置为 1
            if (cnt == 0) {
                majority = nums[i];
                cnt = 1;
            }
        }
    }

    // 第三步:验证候选元素是否是真正的多数元素
    cnt = 0;
    for (int num : nums) {
        // 统计候选元素在数组中出现的次数
        if (num == majority) {
            cnt++;
        }
    }

    // 如果候选元素出现的次数超过数组长度的一半,则返回该元素;否则返回 0(题目保证有解,这里不会返回 0)
    return cnt > nums.length / 2 ? majority : 0;
}

代码注释解释

  1. 第一步:初始化候选元素和计数器
    • 我们从数组的第一个元素开始,将其设为候选的多数元素 majority,并初始化计数器 cnt 为 1。
  2. 第二步:遍历数组寻找候选元素
    • 遍历数组的每个元素:
      • 如果当前元素与 majority 相同,说明它可能是多数元素,计数器 cnt 加 1。
      • 如果当前元素与 majority 不同,说明 majority 的优势减少,计数器 cnt 减 1。
      • 如果 cnt 减到 0,说明当前元素占据了更多的位置,需要重新设定 majority 为当前元素,并将 cnt 重置为 1。
  3. 第三步:验证候选元素
    • 再次遍历数组,统计 majority 在数组中实际出现的次数。
    • 如果 majority 出现次数超过数组长度的一半,则它就是多数元素,返回它;否则返回 0(在这道题目中,题目保证有解,因此这里不会返回 0)。

😄总结

Boyer-Moore多数投票算法在处理出现次数超过一半的数字问题上,提供了一个非常高效的解决方案。它不仅满足了时间复杂度 O(n) 和空间复杂度 O(1) 的要求,而且通过一次遍历就能确定多数元素,非常适合大规模数据的处理。在今后的算法设计中,这种思想也可以应用到其他类似的场景中。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。