This is the 25th day of my participation in the August Genwen Challenge.More challenges in August

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

[LeetCode 448. Find missing numbers in all arrays] – JavaScript(hash table + in place hash)

Topic describes

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.

Subject analysis

This problem is similar to the solution for duplicate data in Leetcode 442. Array. But there are no clear limits on space use.

Solution 1: Hash table

The algorithm flow is as follows:

  • Prepare a hash table map of the structurenumber-boolean
  • Iterate over the array, setting the map value of each element to true
  • From 1 to n, checkmap[i]Whether it is true. If true, it appears in the original array; Otherwise, it doesn’t exist.

This process requires the creation of O(N) space for the hash table in O(N) time. The code is as follows:

var findDisappearedNumbers = function(nums) {
  const length = nums.length;
  if(! length) {return [];
  }
  const map = {};
  nums.forEach(num= > (map[num] = true));
  const res = [];
  for (let i = 1; i <= length; ++i) {
    if(! map[i]) res.push(i); }return res;
};
Copy the code
Solution 2: Hash in place

Similar to the solution for duplicate data in Leetcode 442. Arrays: symbols are used to indicate whether an element has been present. The symbol of the element with the subscript I, indicating whether the element with the value I + 1 is present, minus sign is present, plus sign is not present.

There is no space for the hash table, order N time. The code implementation is as follows:

/ * * *@param {number[]} nums
 * @return {number[]}* /
var findDisappearedNumbers = function(nums) {
  const length = nums.length;
  if(! length) {return [];
  }
​
  nums.forEach(num= > {
    // Make the element with subscript ABS (num) -1 negative
    const absNum = Math.abs(num);
    if (nums[absNum - 1] > 0) {
      nums[absNum - 1] * = -1; }});const res = [];
  // Iterate over array subscripts
  for (let i = 1; i <= length; ++i) {
    // If the element with subscript I -1 is positive, then the integer I does not occur.
    if (nums[i - 1] > 0) { res.push(i); }}return res;
};
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤