【MarsCode】每日一题 之找出整型数组中占比超过一半的数字

找出整型数组中占比超过一半的数字

1.问题描述

小R从班级中抽取了一些同学，每位同学都会给出一个数字。已知在这些数字中，某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。

测试样例

样例1：

输入：array = [1, 3, 8, 2, 3, 1, 3, 3, 3] 输出：3

样例2：

输入：array = [5, 5, 5, 1, 2, 5, 5] 输出：5

样例3：

输入：array = [9, 9, 9, 9, 8, 9, 8, 8] 输出：9

2.思路与题解

1. 理解问题：我们需要找到数组中出现次数超过一半的数字。

2. 数据结构选择：由于我们只需要找到一个数字，不需要额外的数据结构。

3. 算法步骤

   ：

   • 初始化两个变量：candidate 用于存储当前候选数字，count 用于记录当前候选数字的计数。

   • 遍历数组中的每个元素：

     • 如果 count 为 0，将当前元素设为 candidate，并将 count 设为 1。

     • 如果当前元素与 candidate 相同，增加 count。

     • 如果当前元素与 candidate 不同，减少 count。

   • 最终 candidate 就是我们要找的数字。

2.4代码框架

Java

▼
java
复制代码
public class Main {
    public static int solution(int[] array) {
        // Edit your code here
        int candidate = 0;
        int count = 0;
        for(int num : array){
            if (count ==0) {
                candidate=num;
            }
            if (num== candidate) {
                count++;
            }else{
                count--;
            }
        }
        return candidate;
    }

    public static void main(String[] args) {
        // Add your test cases here

        System.out.println(solution(new int[]{1, 3, 8, 2, 3, 1, 3, 3, 3}) == 3);
    }
}

C++

▼
c++
复制代码

Python

▼
python
复制代码

Golang

▼
go
复制代码

2.5一些疑难的代码解释

• candidate 和 count 用于跟踪当前的候选数字和其计数。
• 遍历数组时，根据当前元素更新 candidate 和 count。
• 最终 candidate 就是出现次数超过一半的数字。

3.欢迎大佬们关注或莅临本渣的一些个人website

gitee： https://gitee.com/xiao-chenago github：https://github.com/cool-icu0 语雀：https://www.yuque.com/icu0 csdn：https://cool-icu.blog.csdn.net/