https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/
思想:
由于只能用O(n)时间和O(1)空间,因此只能常数次遍历,且不能用hash
所以先遍历一遍数组,将nums[nums[i]-1]变成负数,即所有出现过的数字i,nums[i]中为负数,所以最后遍历一遍数组,将所有为整数的单元下标+1存储到答案数组中即可。
注意:由于有些数字重复,所以在写代码时注意加入绝对值
js代码示例
/**
* @param {number[]} nums
* @return {number[]}
*/
var findDisappearedNumbers = function(nums) {
let n = nums.length;
for(let i = 0 ; i < n ; i++){
let j = Math.abs(nums[i])-1;
nums[j] = Math.abs(nums[j]) * -1;
}
let ans = [];
for(let i = 0 ; i < n ; i++){
if(nums[i]>0){
ans.push(i+1);
}
}
return ans;
};