力扣(LeetCode)448

共计 605 个字符，预计需要花费 2 分钟才能阅读完成。

题目地址：https://leetcode-cn.com/probl… 题目描述：给定一个范围在 1 ≤ a[i] ≤ n (n = 数组大小) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为 O(n) 的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入:[4,3,2,7,8,2,3,1]
输出:[5,6]
解答：对原数组做映射，把数字 i(i>=1,i<=n) 映射到原数组的 nums[i-1] 上，使得 nums[i-1] 为 -1。然后再扫描一遍数组，如果 numsj 不为 -1，那么 j + 1 就不存在！java ac 代码：
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {

List<Integer>ans = new ArrayList(nums.length);
for(int i = 0;i < nums.length;i++)
{

int loc = nums[i]-1;
if(loc != -2)
while(nums[loc] != -1){
int temp = nums[loc]-1;
nums[loc] = -1;
loc = temp;
}

}
for(int i = 0;i < nums.length;i++)
if(nums[i] != -1)
ans.add(i+1);
return ans;

}
}