每天一道leetcode442-数组中重复的数据

题目

每天一道leetcode442-数组中重复的数据 分类：数组 中文链接： https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/description/ 英文链接 https://leetcode.com/problems/find-all-duplicates-in-an-array/description/

题目详述

给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。 找到所有出现两次的元素。 你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？ 示例： 输入: [4,3,2,7,8,2,3,1] 输出: [2,3]

题目详解

思路

• 由于数组中的数字范围给定了（1到n），所以可以new一个数组array，数组的大小设置为n+1，数组初始化为0;
• 然后遍历给定数组nums,比如nums数组有一个数字4，那么就令array[4] += 1，每出现数字4一次，array[4] += 1这个就进行加1的操作，也就是说统计数字4出现的次数
• 最后遍历数组array,出现的次数大于1，那么就是有重复数字了！

代码

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

代码讲解

• 6-7行 统计nums数组中每个数字出现的个数
• 8-12行 如果array数组中出现的数字大于1了，那么说明重复，就把它加入到result中。