preface

This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions.

The title

Given an array of integers in the range 1 ≤ a[I] ≤ n (n = array size), some of the elements appear twice and others only once.

Find all numbers in the range [1, n] that do not appear in the array.

Can you do this without using extra space and with O(n) time? You can assume that the returned array is not in the extra space.

Example:

Input: [4,3,2,7,8,2,3,1] output: [5,6]Copy the code

Train of thought

We want the given array to be arranged in the correct order, with each number in its proper place. For example, the example of [4,3,2,7,8,2,3,1] would look like [1,2,3,4, 7,8].

Next is very simple, we use an array disappeardNums to store the disappearing array, traversal the new array, but the traversal length must be the original array length, here to pay special attention to, as long as the judgment of the current location whether there isa value, if there is no indication of the location of the number is the disappearing number, Push it into disappeardNums and finally return to disappeardNums.

AC code

New array traversal:

/** * @param {number[]} nums * @return {number[]} */ var findDisappearedNumbers = function(nums) { const disappearedNums = []; const newNums = []; for (let i = 0; i < nums.length; i++) { newNums[nums[i] -1] = nums[i]; } for (let i = 0; i < nums.length; i++) { if (! newNums[i]) { disappearedNums.push(i+1); } } return disappearedNums; };Copy the code

performance

IndexOf way

var findDisappearedNumbers = function(nums) {
    const disappearedNums = [];

    for(let i = 0; i < nums.length; i++) {
        if(nums.indexOf(i+1) < 0) {
            disappearedNums.push(i);
        }
    }

    return disappearedNums;
};
Copy the code

Performance:

conclusion

Here I tried many other methods, such as using new Set to duplicate and then compare, but I found that we did not reserve space, so the key to solve this problem is to reserve space.

So why use the length of the original array instead of the length of the new array? Because if there is no number in the last digit or several digits, JS will automatically remove the last empty space, and the length will become less, so the result of traversal is missing and inaccurate.

Some people say, why not use indexOf? Because this is a loop loop, the performance is worse.