leetCode The first 448 topic Find all the missing numbers in the array
Here's one for you n Array of integers nums , among nums[i] In the interval [1, n] Inside . Please find out all in [1, n] Range but not in nums Number in , And return the result in the form of array .
Example 1：
Input ：nums = [4,3,2,7,8,2,3,1]
Output ：[5,6]
Example 2：
Input ：nums = [1,1]
Output ：[2]
Tips ：
n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
Advanced ： You can use no extra space and the time complexity is O(n) Solve this problem in the case of ? You can assume that the returned array is not included in the extra space .
stay python To determine whether an element is directly used in the list Element name in The list name can determine
dis = [] for i in range(1,len(nums)+1): if i not in nums: dis.append(i)But this way of writing will traverse the whole list every time one element is judged , It will inevitably lead to timeout
And it does not meet the requirements of advanced level in the question , Even if it is recorded as hash map And then retrieve , It also takes up a lot of space
If you want the time complexity to be O(n), And do not occupy the space outside , So we can only use the array itself , It's hard to find inspiration .
With [4,3,2,7,8,2,3,1] For example , We need to associate numbers with subscripts , But it can't be used hash map.
-------------------------------
To find the missing number in a cycle , You have to use the conditions given in the question ： All the numbers are in 1-n Between , We need to make a change , Make his value not in 1-n, In this way, we can find out which numbers are wrong through a range comparison .
-----------------------------
The array itself can only tell us two things , One is the subscript , The other is numerical value , It is necessary to associate the value with the subscript . stay python in , The subscript is from 0 Start , We'll take the first number 4 For example , take 4-1 Get the subscript 3, We will list the 3 Make a transformation of the corresponding value , Make it not 1-n, You might as well add a minus sign directly （ You can also add n, Make the scope out of 1-n）, Get is -7, For the second element 3, Subscript 2 The expected value becomes negative , obtain -2, If it's already negative , You don't have to change .
------------------------------
such [4,3,2,7,8,2,3,1], It becomes [-4,-3,-2,-7,8,2,-3,1], So we can see the subscript 4,5 The corresponding value is an integer . because python Subscript from 0 Start , So the corresponding is missing 5 and 6.
-------------------------------
Because the data is missing 5,6 So we can't manipulate subscripts 4,5, In turn, , The value corresponding to the subscript has not been changed , It is because the number of operation subscripts is missing .
## python3
class Solution:
def findDisappearedNumbers(self, nums: [int]) -> [int]:
for i in range(len(nums)):
index = abs(nums[i])-1
if nums[index] > 0:
nums[index] = -nums[index]
dis = []
for i in range(len(nums)):
if nums[i] > 0:
dis.append(i+1)
return dis
It can also be used. +n The operation of , Make the value not in 1-n This range , Further judgment
## python3
class Solution:
def findDisappearedNumbers(self, nums: [int]) -> [int]:
n = len(nums)
for i in range(n):
index = (nums[i]-1)%n
nums[index] += n
dis = []
for i in range(n):
if(nums[i] <= n):
dis.append(i+1)
return dis
