# 448. Find All Numbers Disappeared in an Array

Given an array `nums` of `n` integers where `nums[i]` is in the range `[1, n]`, return an array of all the integers in the range `[1, n]` that do not appear in `nums`.

Example 1:

```Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
```

Example 2:

```Input: nums = [1,1]
Output: [2]
```

Constraints:

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

Follow up: Could you do it without extra space and in `O(n)` runtime? You may assume the returned list does not count as extra space.

Problem Analysis: The task is to find all the numbers missing from 1 to n in a given array, which might contain duplicate numbers and should be solved without using extra space (except for the output).

Solution Approach: We can leverage the array itself by marking the presence of numbers. Specifically, we traverse the array and turn the number at the index corresponding to each encountered number into negative as a mark. Since the numbers in the array are all supposed to be between 1 and n, we can directly use the number value as the array index.

Time and Space Complexity Analysis: The time complexity is O(n), as we only need to traverse the array twice. The space complexity is O(1), as no extra space is used apart from the output.

Conclusion: This method effectively utilizes the structure of the array itself to mark the presence of numbers, thereby identifying the missing ones, while avoiding the use of extra space.

``````function findDisappearedNumbers(nums: number[]): number[] {
let res = [];
for (let num of nums) {
let index = Math.abs(num) - 1;
if (nums[index] > 0) {
nums[index] = -nums[index];
}
}
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
res.push(i + 1);
}
}
return res;
}
``````

``console.log(findDisappearedNumbers([4,3,2,7,8,2,3,1])); // 输出 [5,6]``

This site uses Akismet to reduce spam. Learn how your comment data is processed.