站长统计app官方网站,网站建设的小结,手机官方,保险代理平台给你一个含 n 个整数的数组 nums #xff0c;其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字#xff0c;并以数组的形式返回结果。
示例 1#xff1a;
输入#xff1a;nums [4,3,2,7,8,2,3,1]
输出#xff1a;[5,6]示例 2其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字并以数组的形式返回结果。
示例 1
输入nums [4,3,2,7,8,2,3,1]
输出[5,6]示例 2
输入nums [1,1]
输出[2]
方法一 public ListInteger findDisappearedNumbers(int[] nums) {ListInteger list new ArrayList();HashMapInteger, Integer map new HashMap();for (int i1;inums.length;i){map.put(i,0);}for (int j0;jnums.length;j){if(map.containsKey(nums[j])){ // 如果原来数组有在区间的数字 把value设置为1map.replace(nums[j],1);}}for (Map.EntryInteger, Integer entry : map.entrySet()) {if(entry.getValue().equals(0)) { //获取不在范围内数list.add(entry.getKey());}}return list;} 方法二、
方法一原地修改 思路及解法
我们可以用一个哈希表记录数组 nums数字由于数字范围均在 [1,n][1,n][1,n] 中记录数字后我们再利用哈希表检查 [1,n][中的每一个数是否出现从而找到缺失的数字。
由于数字范围均在 [1,n]中我们也可以用一个长度为 nnn 的数组来代替哈希表。这一做法的空间复杂度是 O(n)O(n)O(n) 的。我们的目标是优化空间复杂度到 O(1)。
注意到 nums 的长度恰好也为 n能否让 nums充当哈希表呢
由于 nums的数字范围均在 [1,n]中我们可以利用这一范围之外的数字来表达「是否存在」的含义。
具体来说遍历 nums每遇到一个数 xxx就让 nums[x−1] 增加 n。由于 nums 中所有数均在 [1,n] 中增加以后这些数必然大于 n。最后我们遍历 nums若 nums[i] 未大于 n就说明没有遇到过数 i1。这样我们就找到了缺失的数字。
注意当我们遍历到某个位置时其中的数可能已经被增加过因此需要对 n 取模来还原出它本来的值。
class Solution {public ListInteger findDisappearedNumbers(int[] nums) {int n nums.length;for (int num : nums) {int x (num - 1) % n;nums[x] n;}ListInteger ret new ArrayListInteger();for (int i 0; i n; i) {if (nums[i] n) {ret.add(i 1);}}return ret;}
} 方法三
public class FindMissingNumber {public ListInteger findDisappearedNumbers(int[] nums) {ListInteger res new ArrayList();HashSetInteger set new HashSet();for (int i 0; i nums.length; i) {set.add(nums[i]);}for (int i 1; i nums.length; i) {if(set.add(i)){res.add(i);}}return res;}
}
