LeetCode Find All Numbers Disappeared in an Array【Easy】
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]
解决
题目主要是找出给定数组中所有不出现的数字，解决该为题主要是找出nums[i]与nums[|nums[i]|-1]其中的关系，我们这边采用取负方法进行求解。代码及部分注释如下
代码
/**
* 找出数组中的值与其值应该在下标的位置关系
* nums[i]与nums[|nums[i]|-1]
* 取负值 如果为正则取该值对应的下标+1
* @param nums
* @return
*/
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<>();
//判断值关系
for(int i=0;i<nums.length;i++){
int index = Math.abs(nums[i])-1;
nums[index]=(nums[index]>0)?(-nums[index]):nums[index];
}
//取出数组中值为正的下标+1
for(int i=0;i<nums.length;i++){
if(nums[i]>0){
res.add(i+1);
}
}
return res;
}
