时间戳

首页 > 解决方案 > 如何更有效地查看数组？Javascript

javascript - 如何更有效地查看数组？Javascript

问题描述

我一直在做很多关于 codility 的实践测试，虽然我所有的解决方案都有效，但它们总是有隐藏的压力测试，其中包括大量数组，例如下面的代码需要使用数组 A 并找到数组中缺少的最低正数序列。

例如：给定 A = [1, 3, 6, 4, 1, 2]，函数应返回 5。5 是i循环中递增的值。i只要在数组中找不到索引，函数就会返回。

它可以正常工作，但 codility 使用 1-100,000 数组对其进行了测试，并且在 6 秒限制时超时。由于同样的原因，我在练习测试中的大部分代码往往会失败。非常感谢任何帮助。

console.log(solution([1, 3, 6, 4, 1, 2]));
function solution(A) {
    let i = 0
    for (i = 1; i <= A.length ; i++){
        if(A.includes(i) == false){
            return i
        }
    }
    return i
}

标签： javascriptarraysloops

解决方案

There is no way to look through N items in less than O(n) which is what you're doing. The issue is you're looking through the array N times as well - this means you run N*N times and can be improved.

The most "typical" way to improve this approach is to use a Set or similar data structure with amortised (usually) constant-time access to elements. In your case this would look like:

console.log(solution([1, 3, 6, 4, 1, 2]))
function solution(A) {
    // build existing elements, in O(N)
    const values = new Set(A)
    let i = 0
    for (i = 1; i <= A.length; i++){
        if(!values.has(i)){
            return i
        }
    }
    return i
}

This runs in O(N) (creating the set) + O(N) iterating the array and performing constant time work each time.

推荐阅读