Howdoyoulookthrougharraysmoreefficiently?Javascript

html5 • • 问答

I've been doing a lot of the practise tests on codility and though all my solutions work, they always have hidden stress tests which include massive arrays, the following code for example needs to take array A and find the lowest positive number missing from the sequence.

e.g: given A = [1, 3, 6, 4, 1, 2], the function should return 5. 5 is the value of i which increments in the loop. Function returns whenever index i is not found in array.

It works correctly but codility tested it with a 1-100,000 array and it timed out at the 6 second limit. most of my codes on the practise tests tend to fail for the same reason. Any help greatly appreciated.

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
}

回答

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.

  • I did not know that creating the Set was itself `O(N)` - if so then that greatly simplifies things!
以上是Howdoyoulookthrougharraysmoreefficiently?Javascript的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>
相关内容