1、前言

2、思路

采用桶排序的思路，只不过桶排序需要开辟新数组，而题目中的原数组就是长度为 n，且数组中数字是 1-n，说明可以将原数组原地桶排序。

采用遍历两边的思路，第一遍将 nums[i] != nums[nums[i] - 1] 的数交换；第二遍如果 i != nums[i] - 1 则说明它无处安放，直接选它即可。如果是一遍的话，那交换过程中可能会选到重复的，只能修改原来数字或者用 set，不推荐。

3、代码

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        if(nums == null || nums.length == 0){
            return new ArrayList<>();
        }
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            while(nums[i] != nums[nums[i] - 1]){
                swap(nums, i, nums[i] - 1);
            }
//            // 这种会出现重复的，所以要在外边，要不然只能用 set
//            if(i != nums[i] - 1 && nums[i] == nums[nums[i] - 1]){
//                list.add(nums[i]);
//            }
        }
        for(int i = 0; i < nums.length; i++){
            if(i != nums[i] - 1 && nums[i] == nums[nums[i] - 1]){
                list.add(nums[i]);
            }
        }
        return list;
    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}