您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

消失的数字(图文)

第十三双眼睛2024-01-22【数据结构与算法】人已围观

简介消失的数字
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

思路1：先遍历一遍数组，将数组存放在一个map中，因为每个元素都是在n以内，因此，循环1-n，判断每个数是否在map中，如果不在，就加入结果集中，最后进行返回。代码如下：

public static List<Integer> method1(int[] nums) {
   List<Integer> list = new ArrayList<>();
   if (nums == null || nums.length == 0) {
       return list;
   }
   Map<Integer,Integer> map = new HashMap<>();
   for (int i = 0; i < nums.length; i ++) {
       map.put(nums[i], i);
   }
   for (int i = 1; i<= nums.length; i ++) {
       if (map.get(i) == null) {
           list.add(i);
       }
   }
   return list;
}

思路2：上面的方法多开辟了一个map的空间，其实可以在原数组上进行操作，因为，数组的每个元素都是n以内的，因此遍历到每个元素，这个元素减一对应的下标也必然在这个数组中，因此，遍历一遍数组，对每个元素进行如此操作，重复的元素必然会进行两遍操作，而没有出现的元素必然会操作不到，利用这种特性，就可以找到未出现的元素，注意，在操作的过程中，会改变其中的一些元素，为了能从改变后的元素还原原本的元素，我们的操作可以是给原来的元素上加n，这样，还原时只需要对n取模就可以了。代码如下：

public static List<Integer> method2(int[] nums) {
   List<Integer> list = new ArrayList<>();
   if (nums == null || nums.length == 0) {
       return list;
   }
   int length = nums.length;
   for (int i = 0; i < length; i ++) {
       int x = (nums[i] - 1) % length;
       nums[x] += length;
   }

   for (int i = 0; i < length; i++) {
       if (nums[i] <= length) {
           list.add(i+1);
       }
   }
   return list;
}

Tags：

很赞哦！ ()

上一篇：移动零(图文)

下一篇：回文链表(图文)