Leetcode第442题

题目描述

https://leetcode.cn/problems/find-all-duplicates-in-an-array/

个人思路

对于要求nums里重复整数，我想的是创建一个新数组，将下标当作整数，然后遍历一遍nums，对新数组的整数下标为+1，然后遍历完之后再遍历一遍新数组，如果这个数>1，则将这个数的下标进行保存，最后输出。

   public List<Integer> findDuplicates(int[] nums) {
     int[] temp=new int[nums.length];
     for (int num:nums)temp[--num]++;
     List<Integer> list=new ArrayList<>();
     for (int i=0;i<temp.length;i++){
         if (temp[i]>1)list.add(i+1);
     }
     return list;
 }

代码优化

无

参考思路

我使用的方法，新创建了一个数组，看到一个新的思路只使用的原数组进行操作。

遍历原数组，还是将这个数当作下标，将改下标的数置为负数，只要发现数组中这个数为负数，说明已经访问过一遍。则将其下标保存，最后输出。

public List<Integer> findDuplicates(int[] nums) {
     List<Integer> duplicates = new ArrayList<>();

     for (int i = 0; i < nums.length; i++) {
         int index = Math.abs(nums[i]) - 1;

         if (nums[index] < 0) {
             duplicates.add(index + 1);
         } else {
             nums[index] = -nums[index];
         }
     }
     return duplicates;
 }

收获

这个在原数组基础上添加信息，但不影响原数组正常使用的方式值得学习。