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.length1 <= n <= 1051 <= 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.
题目分析： 这个问题要求我们找出在1到n之间但没有出现在给定数组中的所有数字。数组中可能有重复数字，且没有额外空间使用（除了输出结果之外）。
解题思路： 我们可以利用数组自身，通过标记已存在的数字来找出缺失的数字。具体来说，我们可以遍历数组，并将出现的数字对应位置上的数值变为负数，作为标记。因为数组中的数字都应该在1到n之间，所以可以直接用数字值作为数组索引。
代码实现：
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;
}
时间和空间复杂度分析： 时间复杂度为O(n)，因为我们只需要遍历数组两次。空间复杂度为O(1)，因为除了输出结果外，我们没有使用额外的空间。
测试用例：
console.log(findDisappearedNumbers([4,3,2,7,8,2,3,1])); // 输出 [5,6]总结： 这个方法有效地利用了数组本身的结构来标记存在的数字，从而找出缺失的数字，同时避免了额外的空间使用。