This is the 23rd day of my participation in the August More Text Challenge.More challenges in August

Find missing numbers in all arrays (item number 448)

The title

Give you an array of n integers nums, where nums[I] is in the interval [1, n]. Find all numbers in the range [1, n] that do not appear in NUMs and return the result as an array.

Example 1:

Enter: nums = [4.3.2.7.8.2.3.1] output: [5.6]
Copy the code

Example 2:

Enter: nums = [1.1] output: [2]
Copy the code

Tip:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n

Advanced: Can you solve this problem in O(n) time without using extra space? You can assume that the returned array is not in the extra space.

link

Leetcode-cn.com/problems/fi…

explain

This one, this one is the five ways to write hui

It looks really simple on the surface, and there are many solutions that can be thought of, and the main idea is still one.

Scan the array, record the numbers that meet the criteria, and then scan the second time for the corresponding processing, because there are too many solutions, not to explain here, 👇 will be introduced in turn.

Your own answer (includes)

If the number is not in the array, it is pushed directly into the RES, and then returns the RES when the loop is complete.

var findDisappearedNumbers = function(nums) {
  const res = []
  let count = 1
  while (count <= nums.length) {
    if(! nums.includes(count)) res.push(count) count++ }return res
};
Copy the code

Using the for loop is also possible, personal preference

Your own answer (set+ initialization)

We can also use set to process nums directly, so that duplicate numbers in the array are filtered out directly. Later, we use set.has to determine whether the current number is in the set, if it is, and if it is not, we push it into the RES.

This method is faster than the previous method because the performance of HAS is better than that of includes. However, with set, the space complexity becomes O(n), the memory footprint is more than the previous method, and the typical space change time is more.

var findDisappearedNumbers = function(nums) {
  const set = new Set(nums)
  const res = []
  let count = 1
  while (count <= nums.length) {
    if(! set.has(count)) res.push(count) count++ }return res
};
Copy the code

Your own answer (set+ change in place)

This method is essentially the same as the above method, except that no RES is required and only the modified set is returned

We initialize a set, and then we loop through the array, and if it’s in the set, we delete it from the set, and if it’s not in the set, we add it, and we’re done

All that is left is the element that does not appear in NUMS. It is very simple, and the res variable is omitted. The disadvantage is that the add, set, and delete operations can be time-consuming.

var findDisappearedNumbers = function(nums) {
  const set = new Set(nums)
  for (let i = 1; i <= nums.length; i++) {
    if (set.has(i)) {
      set.delete(i)
    } else {
      set.add(i)
    }
  }
  return Array.from(set)
};
Copy the code

A better way (two loops)

In fact, the three methods of 👆 do not meet the question, the space complexity is not up to the standard, even if the standard performance loss will be relatively large, there is no better method?

Apparently there is, and officials have come up with a way to modify it based on NUMS.

Let’s go back to the definition of an array, which is essentially an object of property type key, or index. Is it possible to combine index and value in a wave of coordination to count elements that do not exist?

First, we can convert the value and index, that is, nums as index, add n to the value of all indexes found, then if some number does not appear, then the value of the index represented by the number must not be greater than N. If it already exists, the value will be greater than n because of the operation just done. If the value of the current number is less than or equal to n, then the number did not appear. Push res.

It may be more around, look at the code to understand 👇 :

var findDisappearedNumbers = function(nums) {
  const len = nums.length
  const res = []
  for (const num of nums) {
    const x = (num - 1) % len
    nums[x] += len
  }
  for (let i = 0; i < len; i++) {
    if (nums[i] <= len) res.push(i + 1)}return res
};
Copy the code

The for loop is used twice: once to update the array to determine which numbers are present; The second is used for recording, pushing nonexistent numbers into the RES.

Overall relatively simple, is difficult to think of it, there is no way ~





PS: To view previous articles and titles, click on the links below:

Here are the categories by date 👇

Front end Brush – Table of Contents (date category)

After some friends remind, the feeling should also be classified according to the question type here is classified according to the question type 👇

Front End Brush problem path – Table of Contents (Question type classification)