小学生都能看懂的题解 | #数组中出现次数超过一半的数字#

问题描述

假设你有一堆小球，这些小球有不同的颜色。现在有人告诉你，这堆小球里有一种颜色的小球特别多，多到超过了所有小球数量的一半。你的任务就是找出这种特别多的颜色是什么。

解决方案

我们可以用一个聪明的办法来找出那种颜色。这个办法叫做“摩尔投票法”，听起来很高大上，其实很简单！

方法步骤

1. 选代表：从这堆小球里随便挑一个出来，把它当成“代表”。
2. 计票：
1. 拿一个新的小球跟“代表”比较。
2. 如果颜色一样，我们就认为“代表”更有可能是对的那个颜色，所以我们给它加一票。
3. 如果颜色不一样，我们就认为“代表”的优势减少了一点，所以就给它减一票。
3. 换代表：如果“代表”的票数变成了0，我们就换个新的小球当“代表”，然后继续计票。
4. 重复步骤：一直重复上面的过程，直到所有的球都检查完了。

最后验证

• 我们得到了一个可能是最多的颜色，但我们还需要再确认一下。重新数一遍，看看这个颜色的小球是不是真的超过了总数的一半。

示例代码解释

现在让我们用更简单的语言解释一下上面的代码。

public class FindColor {
    public int MoreThanHalfNum_Solution(int[] balls) {
        if (balls == null || balls.length <= 0) {
            throw new IllegalArgumentException("没有小球！");
        }

        int color = balls[0]; // 选出第一个小球的颜色作为代表
        int votes = 1; // 初始给代表一票
        
        // 开始计票
        for (int i = 1; i < balls.length; i++) {
            if (votes == 0) { // 如果代表的票数为0，换一个新的代表
                color = balls[i];
                votes = 1;
            } else if (balls[i] == color) { // 如果颜色相同，增加一票
                votes++;
            } else { // 如果颜色不同，减少一票
                votes--;
            }
        }
        
        // 最后验证
        if (!checkIfMoreThanHalf(balls, color)) {
            throw new RuntimeException("找不到超过一半的颜色！");
        }
        
        return color; // 返回最多的颜色
    }

    private boolean checkIfMoreThanHalf(int[] balls, int color) {
        int count = 0;
        for (int ball : balls) {
            if (ball == color) {
                count++; // 计数颜色相同的球
            }
        }
        return count > balls.length / 2; // 判断是否超过一半
    }

}

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。