/**
Given an array nums of n integers where nums[i] is in the range [1, n], return
an array of all the integers in the range [1, n] that do not appear in nums.
Example 1:
Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
Example 2:
Input: nums = [1,1]
Output: [2]
Constraints:
n == nums.length
1 <= n <= 10⁵
1 <= nums[i] <= n
Follow up: Could you do it without extra space and in O(n) runtime? You may
assume the returned list does not count as extra space.
Related Topics数组 | 哈希表
👍 1107, 👎 0
*/
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> result = new ArrayList<>();
int num = nums.length;
for (int i = 0; i < num; i++) {
int index = (nums[i] - 1) % num;
nums[index] = nums[index] + num;
}
for (int i = 0; i < num; i++) {
if (nums[i] <= num) {
result.add(i + 1);
}
}
return result;
}
}
//leetcode submit region end(Prohibit modification and deletion)
