时间戳

首页 > 解决方案 > 仅针对大数据查找数组中最大数的总数失败

javascript - 仅针对大数据查找数组中最大数的总数失败

问题描述

我做了一些 Hackerrank 挑战来提高我解决问题的能力，所以其中一个挑战是从一组数字中找到最大的总数。例如，如果我们有3 2 1 3 1 3它应该返回3

这就是我所做的：

function birthdayCakeCandles(ar) {
let total= 0
let sortedArray = ar.sort((cur,next)=>{
    return cur<next
})

ar.map(item => {
    if(item===sortedArray[0]) {
        total ++;
    }
    })
return total
}

所以我对给定的数组进行了排序，然后通过数组映射并检查有多少数字等于该数组中的最大数字并计算总数。

这将通过 8/9 测试用例，其中一个测试用例有一个长度为 100000 的数组，对于这个它失败了，这是这个测试用例的给定数据。

真的不明白为什么它在这个测试中失败了，这可能是因为 JavaScript 总是同步和单线程的吗？

我尝试使用 Promise 和 async await，但hackerrank 会将第一个返回视为输出（即 Promise 本身）并且它不使用 resolve 值作为输出，因此无法真正对此进行测试。

是不是我的逻辑有问题？

标签： javascriptarraysnode.js

解决方案

排序方法太慢（O(n log n) 时间复杂度）。对于 HR 的算法挑战，像 promises/async 这样对你的语言选择有些特殊的功能不太可能拯救你。

您可以使用一个对象一次性完成此操作，以跟踪您“看到”每个数字的次数和数组的最大数量，然后简单地索引对象以获得您的答案：

function birthdayCakeCandles(ar) {
    let best = -Infinity;
    const seen = {};

    for (let i = 0; i < ar.length; i++) {
        if (ar[i] > best) {
            best = ar[i];
        }

        seen[ar[i]] = ++seen[ar[i]] || 1;
    }

    return seen[best];
}

时间和空间复杂度：O(n)。

编辑：

这个答案更好，空间恒定（在 JS 中）：

function birthdayCakeCandles(ar) {
    let best = -Infinity;
    let count = 0;

    for (const n of ar) {
        if (n > best) {
            best = n;
            count = 1;
        }
        else if (n === best) {
            count++;
        }
    }

    return count;
}

推荐阅读