javascript - Codility MissingInteger Javascript 解决方案(提案)

Question

今天下午我尝试解决Codility的demo测试。在思考了如何提高性能(并进行了一些搜索)之后，我创建了以下代码:

function solution(A) {
    let array = [...Array(1000001).keys()];

    const onlyPositives = A.filter(n => n>0);
    if(onlyPositives.length == 0) return 1

    onlyPositives.forEach(a => {
        if(array[a] != null)
            array[a] = null;
    });
    array[0] = null;

   return array.findIndex(e => e != null);
}

有人有其他想法吗？

Answer 1

O(n) 解决方案 javascript。使用两个循环。第一个循环将所有大于 0 的元素放入映射/对象中第二个循环检查映射中是否存在值。

function solution(A) {
    let obj = {};
    let min = 1;

   //iterate over all items in the array and store the value in a object;
    for (let i = 0, len=A.length; i < len; i++) {
        const num = A[i];
        if (num > 0) {
            obj[num] = true;
        }
    }
    //start with min===1 check if it's in the object
    // if it is if it's in the object then increment min and repeat until min not in object.
    while (obj[min]) {
        min++;
    }
    //this will return the smallest value not in array bigger or equal to 1
    return min;
}