8.找出整形数组中占比超过一半的数

刷题前请喊一遍我们的口号：

• 方法不对，刷题白费。
• 节省时间，精准刷题。

本题难度系数：⭐简单

问题描述

小 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

解题思路

这个问题是要找出数组中出现次数超过一半的数字。最优解可以使用摩尔投票算法，该算法的时间复杂度是 O(n)，空间复杂度是 O(1)，非常高效。

摩尔投票算法的核心思想：

1. 初始化：假设第一个元素是候选众数，计数器count设为 1。
2. 遍历数组：
   • 如果当前数字等于候选众数，count加 1。
   • 否则，count减 1。
   • 如果count减到 0，更换候选众数为当前数字，并重置count为 1。
3. 最终验证：由于题目保证存在众数，所以候选众数就是答案。

JavaScript 实现

function solution(array) {
    let candidate = array[0];
    let count = 1;

    for (let i = 1; i < array.length; i++) {
        if (count === 0) {
            candidate = array[i];
            count = 1;
        } else if (array[i] === candidate) {
            count++;
        } else {
            count--;
        }
    }

    return candidate;
}

function main() {
    console.log(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) === 3); // true
    console.log(solution([5, 5, 5, 1, 2, 5, 5]) === 5);       // true
    console.log(solution([9, 9, 9, 9, 8, 9, 8, 8]) === 9);    // true
}

main();

代码说明

1. **candidate**：存储当前的候选众数。
2. **count**：记录候选众数的相对出现次数。
3. 遍历数组：根据当前数字调整count，并在count归零时更换候选众数。
4. 返回结果：由于题目保证存在解，直接返回candidate即可。

这个解法是最优的，因为它只需要一次遍历，且没有使用额外空间。

以上关于8.找出整形数组中占比超过一半的数的文章就介绍到这了，更多相关内容请搜索码云笔记以前的文章或继续浏览下面的相关文章，希望大家以后多多支持码云笔记。