数组中重复的数字

题目描述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

限制：
2 <= n <= 100000

题目链接

Leetcode

题目解答

解法一

用一个大小相等的数组array记录下标为num的元素重复次数，如果重复次数大于1，则该元素为重复元素，就是需要返回的结果。

时间复杂度:$O(n)$ 空间复杂度:$O(n)$

class Solution {
    public int findRepeatNumber(int[] nums) {
        int[] array = new int[nums.length];
        for (int num : nums) {
            if (array[num] > 0) {
                return num;
            } else {
                array[num]++;
            }
        }
        return -1;
    }
}

执行用时：1 ms, 在所有 Java 提交中击败了83.55%的用户
内存消耗：46 MB, 在所有 Java 提交中击败了84.31%的用户

解法二

与解法一类似，把数组换成Hash表，添加元素的时候判断Hash表中是否已经存在该元素，如果存在，就把当前元素返回。

时间复杂度:$O(n)$ 空间复杂度:$O(n)$

class Solution {
    public int findRepeatNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.add(num)) {
                return num;
            }
        }
        return -1;
    }
}

执行用时：5 ms, 在所有 Java 提交中击败了47.78%的用户
内存消耗：48.3 MB, 在所有 Java 提交中击败了15.04%的用户

解法三

解法一和解法二的空间复杂度都为$O(n)$，不能继续优化，我们可以换一种处理方式，同样是遍历数组，由于数组中元素范围是在0～n-1，没有重复元素的时候，每个元素在数组中的位置都是唯一的，通过把数组元素的值交换到值所对应的数组下标位置，我们只需要一个临时变量temp就能完成交换过程，如果要交换的两个元素值相等，那么存在重复元素，把当前元素返回。

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

class Solution {
    public int findRepeatNumber(int[] nums) {
        int temp;
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }
                temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        return -1;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：46.1 MB, 在所有 Java 提交中击败了72.16%的用户