LeetCode442——数组中重复的数据

电玩女神 2022-01-21 06:09 180阅读 0赞

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCode]

原题链接：[https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/][https_leetcode-cn.com_problems_find-all-duplicates-in-an-array]

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70][]

知识点：数组

### 思路一：哈希表 ###

显然，这个思路没有利用好题目所给的条件——1 <= a\[i\] <= n。

时间复杂度和空间复杂度均是O(n)，其中n为数组的长度。

JAVA代码：

public class Solution {
    
        public List<Integer> findDuplicates(int[] nums) {
            List<Integer> result = new ArrayList<>();
            int[] array = new int[nums.length + 1];
            for (int i = 0; i < nums.length; i++) {
                if (array[nums[i]] == nums[i]) {
                    result.add(nums[i]);
                } else {
                    array[nums[i]] = nums[i];
                }
            }
            return result;
        }
    
    }

LeetCode解题报告：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 1][]

### 思路二：对数组进行重排序，与[LeetCode041——缺失的第一个正数][LeetCode041]同样的思路 ###

由于题目规定1 <= a\[i\] <= n，因此我们可以对数组进行重排序，令索引为i处的值为i + 1。接着再遍历一遍数组，一旦发现不满足索引i处的值是i + 1这个条件的，该索引处的值就是重复元素。

时间复杂度是O(n)，其中n为数组的长度。空间复杂度是O(1)。

JAVA代码：

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

LeetCode解题报告：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 2][]

### 思路三：将出现过的数字 - 1对应索引的数变为相反数 ###

还是为了利用条件1 <= a\[i\] <= n，我们可以将出现过的数字 - 1对应的索引的数置为原数的相反数。需要注意的是，由于可能存在后续遍历到的nums\[i\]已经在之前被置为相反数的情况，因此**取索引时需要加绝对值**。

时间复杂度是O(n)，其中n为数组的长度。空间复杂度是O(1)。

JAVA代码：

public class Solution {
    
        public List<Integer> findDuplicates(int[] nums) {
            List<Integer> result = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                int temp = Math.abs(nums[i]);
                if (nums[temp - 1] > 0) {
                    nums[temp - 1] *= -1;
                } else {
                    result.add(temp);
                }
            }
            return result;
        }
    
    }

LeetCode解题报告：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 3][]

[https_github.com_617076674_LeetCode]: https://github.com/617076674/LeetCode
[https_leetcode-cn.com_problems_find-all-duplicates-in-an-array]: https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70]: /images/20220121/3294e51c07534564b8512c93738e8de2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 1]: /images/20220121/b0cb7a2012174f6cb62e8648be832669.png
[LeetCode041]: https://blog.csdn.net/qq_41231926/article/details/82656191
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 2]: /images/20220121/16e83fca96934ed59de845075fdf068a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 3]: /images/20220121/545ea0c9c347487bad131270acd6ba94.png