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

Question

我做了一些 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 本身）并且它不使用解析值作为输出，因此无法真正测试这一点。

我的逻辑有问题吗？

Answer 1

排序方法太慢（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;
}