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]
public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List res = new ArrayList();
int size = 0;
for(int i=0;i<nums.length;i++){
if(nums[i]>size){
size = nums[i];
}
}
if(nums.length > size){
size = nums.length;
}
int[] arr = new int[size+1];
for(int i=0;i<nums.length;i++){
arr[nums[i]]++;
}
for(int i=1;i<arr.length;i++){
if(arr[i] ==0){
res.add(i);
}
}
return res;
}
}
本站原创文章皆遵循“署名—非商业性使用—相同方式共享 4.0 协议 (CC BY-NC-SA 4.0)”。共享、演绎请保留以下标注：
原文作者：Jake Tao，来源：「LeetCode – 448. Find All Numbers Disappeared in an Array」
