448. Find missing numbers in all arrays | swipe and punch

create by db on 2021-3-6 16:46:24

Recently revised in 2021-3-6 16:56:30

Idle time to have a tight mind, busy time to have leisure fun

Find missing numbers in all arrays

directory

  • Topic describes
  • Thought analysis
  • AC code
  • conclusion

Topic describes

Returns the directory

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

Thought analysis

Idea 1: Traverse the search

Given that the range of elements in the array is 1-N, the array is traversed from 1 to n to find whether the elements exist, and the ones that do not exist are put into the new array. Time complexity O(n), space complexity O(1)

Idea 2: Array permutation

Use the subscript of the array to mark the presence or absence of a number. Mark all existing numbers by iterating over them (replaced with negative values)

Once again, the index +1 of the positive elements in the array is the missing number.

 

AC code

Solution 1: Traverse the search

/ * * *@param {number[]} nums
 * @return {number[]}* /
var findDisappearedNumbers = function (nums) {
  // Declare a new array
  let arr = []
  // Iterate over the number between 1 and the array length
  for (let i = 1; i <= nums.length; i++) {
    // If the current array does not exist, add a new array
    if (nums.indexOf(i) === -1) {
      arr.push(i)
    }
  }
  return arr
}
Copy the code

Array permutation

/ / input,3,2,7,8,2,3,1 [4]
// Array elements range from 1 to n, where n is the array length and 0-(n-1) is the numeric element subscript
Math.abs(nums[I])-1 is negative, indicating that nums[I] is present
// Elements greater than 0 (subscript +1) are missing from the array
for (let i=0; i<nums.length; i++){
let newIndex = Math.abs(nums[i]) - 1
if (nums[newIndex] > 0) {
nums[newIndex] \*= -1}}// The array changes to [-4,-3,-2,-7,8,2,-3,-1]

Copy the code
/ * * *@param {number[]} nums
 * @return {number[]}* /
var findDisappearedNumbers = function (nums) {
  // Declare a new array
  let arr = []
  // Iterate over the array
  for (let i of nums) {
    // Replace the element with subscript I with a negative value
    // Use math.abs () to make sure the absolute value is positive
    nums[Math.abs(i) - 1] = -Math.abs(nums[Math.abs(i) - 1])}for (let j in nums) {
    // Missing elements (greater than 0) are equal to subscript +1
    if (nums[j] > 0) {
      arr.push(j + 1)}}return arr
}
Copy the code

conclusion

Returns the directory

Cabbage dog with pinched soft persimmon…

Go see cherry blossoms tomorrow!

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign

Postscript: Hello friends, if you think this article is good, remember to give a thumbs-up or star, your thumbs-up and star is my motivation to write more and richer articles!Making the address

Document agreement



dbThe document library 由 dbusingCreative Commons Attribution – Non-commercial Use – Same way Share 4.0 International LicenseGrant permission.

Based on thegithub.com/danygitgitOn the creation of works.

Use rights other than those authorized by this License agreement may be obtained fromCreativecommons.org/licenses/by…Obtained.