leetCode-442:Find All Duplicates in an Array

问题描述

给定一个长度为 n 的整数数组，数组元素的范围 1 ~ n，数组元素出现的次数为 1 次或 2 次，要求找出出现 2 此的元素。题目链接：**点我**

样例输入输出

输入：[4,3,2,7,8,2,3,1]

输出：[2,3]

输入：[1,1,2]

输出：[1]

问题解法

此解法参考：https://leetcode.cn/problems/find-all-duplicates-in-an-array/solution/shu-zu-zhong-zhong-fu-de-shu-ju-by-leetc-782l。主要是判断元素 i 位置的元素是否是 i + 1，如果不是则将 i 位置与 nums[i] - 1 位置的元素互换，直到相等。此时有两种情况，要么 i 位置的元素刚好是 i + 1，要么 i 位置的元素与 nums[i] - 1 的位置元素是相同的（即重复）。最后变量数组，将 i 位置元素不等于 i + 1 的元素找出来组成列表，就是求解的答案。代码如下

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != nums[nums[i] - 1]) {
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] - 1 != i) {
                result.add(nums[i]);
            }
        }
        
        return result;
    }
}

参考资料

https://leetcode.cn/problems/find-all-duplicates-in-an-array/solution/shu-zu-zhong-zhong-fu-de-shu-ju-by-leetc-782l/