448. 找到所有数组中消失的数字 - 力扣(LeetCode)
题目描述:
给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围
但没有出现在 nums 中的数字,并以数组的形式返回结果。
示例:
输入:nums = [4,3,2,7,8,2,3,1]
输出:[5,6]
方法一:Set集合 去重,遍历,查找没有出现的数
思路:Set集合中存放不重复的元素,先将原数组遍历添加到Set集合中去重,再遍历数字1—n,Set中没有的数,可以添加到集合中,也就是没有出现的数,添加到List中。
public List<Integer> findDisappearedNumbers(int[] nums){
List<Integer> list = new ArrayList<>();
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
}
for (int i = 1; i < nums.length+1; i++) {
if (set.add(i)){
list.add(i);
}
}
return list;
}
方法二:
原地修改,数组中的值是1—n,数组下标是0—n-1;因此可以用数组中的数值-1 ,来标记已经出现的数。下面将找到的索引的值加n标记,因此遍历后,不大于n的数,其下标+1,就是未出现的数。
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> list = new ArrayList<>();
int n = nums.length;
for(int num:nums){
int x = (num-1)%n;//有的数会添加两次或两次以上,取模确保数组不越界
nums[x] += n ;
}
for (int i = 0; i < n; i++) {
if (nums[i]<=n){
list.add(i+1);
}
}
System.out.println(list.toString());
return list;
}
}