力扣每日一题2022-05-08中等题：数组中重复的元素

题目描述

思路

交换元素位置

由于给定的n个数都在[1, n]的范围内，若某数字出现了两次，则[1, n]中必然有数字没有出现过。因此，可以将每个数字放在对应的位置。由于数组下标范围是[0, n-1]，所以需要将数字i放在数组中下标为i-1的位置：

如果i恰好只出现一次，则将i放在数组中下标i-1的位置即可； 如果i出现了两次，那么我们希望其中的一个i放在数组下标中为i-1的位置，另一个i放置在任意[不冲突]的位置j。也就是说数j+1没有在数组中出现过。 如果按照上述规则放置数，则只需要对数组进行一次遍历。当遍历到位置i时，如果nums[i]-1≠i，则说明nums[i]出现了两次，就可以把nums[i]放入答案。 放置的方法如下：对数组进行一次遍历。当遍历到位置i时，我们知道nums[i]应该被放在位置nums[i]-1。因此交换nums[i]和nums[nums[i]-1]即可，直到待交换的两个元素相等为止。

Python实现

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            while nums[i] != nums[nums[i] - 1]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        return [num for i, num in enumerate(nums) if num - 1 != i]

Java实现

class Solution {
          
   
    public List<Integer> findDuplicates(int[] nums) {
          
   
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
          
   
            while (nums[i] != nums[nums[i] - 1]) {
          
   
                swap(nums, i, nums[i] - 1);
            }
        }
        List<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i) {
          
   
            if (nums[i] - 1 != i) {
          
   
                ans.add(nums[i]);
            }
        }
        return ans;
    }

    private void swap(int[] nums, int index1, int index2) {
          
   
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}