LeetCode——442.数组中重复的数据

大佬，牛！！！

• 题目：题目其实很容易理解。就是有一个长度为n的数组，内容是1-n之间的，然后每个数都会出现一次或者两次，所以说有些数不会出现，然后让我们统计出现两次的数都有哪些。但是时间要求是o（n），空间要求是o（1）。
• 我的思路：我没想到，空间是o（1）的，我想到的是用一个set即可。如果每次加入，set发现已经有了，则加入链表，如果没有就加入set。但是我的思路也是能过的，不过肯定不符合要求啊。
• 大佬思路1：就是我们先用一遍for，将每个数都再放其对应的下标上，然后再遍历一遍，如果跟下标不一样，则就是只出现了一遍的。这里注意，其实应该下标-1。并且第一次遍历的时候的条件是保证当前这个数等于这个数应该所在的位置。
• 大佬思路2：就是我们对一个位置的数加正负号，例如第i位置上的数的绝对值是a，那么我们对a-1位置的数进行加符号，如果这是第一次出现，则a-1位置一定是一个正数，那么我们修改成负数，否则就是出现过一次了，我们将i位置的数加入到集合中即可，也就是a。
• 技巧：主要是有个规律，就是如果出现了，放在对应位置是准备错的，那么没有放在对应位置的，其实就是没有出现的，而没有出现的这些位置上面的内容，就是出现了两次的。

java代码——我的思路

class Solution {
    public List findDuplicates(int[] nums) {
        Set set = new HashSet<>();
        List list = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                list.add(nums[i]);
            } else {
                set.add(nums[i]);
            }
        }
        return list;
    }
}

java代码——大佬思路1

class Solution {
    public List findDuplicates(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            while (nums[i] != nums[nums[i] - 1]) {// 保证i位置放的是i-1，只要不是就要一直交换
                swap(nums, i, nums[i] - 1);
            }
        }
        List ansList = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            if (nums[i] - 1 != i) {
                ansList.add(nums[i]);
            }
        }
        return ansList;
    }


    public void swap(int[] nums, int idx1, int idx2) {
        int temp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = temp;
    }
}

java代码——大佬思路2

class Solution {
    public List findDuplicates(int[] nums) {
        int len = nums.length;
        List ansList = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            int a = Math.abs(nums[i]);
            if (nums[a - 1] > 0) {// a第一次出现，那么a-1对应的位置的元素一定是正数
                nums[a - 1] = -nums[a - 1];
            }else {// 第二出现，则直接把a放入集合
                ansList.add(a);
            }
        }
        return ansList;
    }
}

• 总结：题目不是很难，但是主要是思路比较难想，算是长经验了。并且大佬思路1中的swap，是不能用之前说到的数学公式a+=b,b-=a,b-=a的形式。最后附上大佬的链接。