[LeetCode] 448. Find All Numbers Disappeared in an Array
文章目录
Problem
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]
Solution
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0) return res;
for (int i = 0; i < nums.length; i++) {
int index = nums[i] > 0 ? nums[i]-1 : -nums[i]-1;
if (nums[index] < 0) continue;
nums[index] *= -1;
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) res.add(i+1);
}
return res;
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论