【刷题笔记】leetCode448找到缺失的数

常规解法

public List<Integer> findDisappearedNumbers(int[] nums) {HashMap<Integer,Integer> numMap = new HashMap<>();for (int i = 0;i<nums.length;i++){if (numMap.get(nums[i]) == null){numMap.put(nums[i],i);}}List<Integer> result = new ArrayList<>();int n=0;for (int t = 1;t<=nums.length;t++){if (numMap.get(t) == null) result.add(t);}return result;}

使用多余的空间HashMap来存放出现过的数字，遍历两次得到没有出现得数字

不使用额外空间的解法

public List<Integer> findDisappearedNumbers(int[] nums) {for (int num : nums){if (nums[Math.abs(num) - 1] > 0) {nums[Math.abs(num) - 1] *= -1;}}List<Integer> numList = new ArrayList<>();for (int i = 0;i<nums.length;i++){if(nums[i] > 0) numList.add(i+1);}return numList;}

直接使用数组本身进行标记，把出现过的数字下标上的数字改成负数，这样再次遍历检查不是负数的数字下标加一就是没出现的数字。