题目

找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：
2 <= n <= 100000

解题思路

1、遍历+计数器

在遍历数组过程中，更新计数器的值，根据计数器的值是否大等于 2 来判断该字符是否出现过。

• 时间复杂度：O(n)。
  • 遍历数组一遍。添加元素的时间复杂度为 O(1)，故总的时间复杂度是 O(n)。
• 空间复杂度：O(n)。不重复的每个元素都可能存入集合，因此占用 O(n) 额外空间

2、原地交换

题目说明尚未被充分使用，即 在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内 。 此说明含义：数组元素的 索引 和 值 是 一对多 的关系。
因此，可遍历数组并通过交换操作，使元素的 索引 与 值 一一对应（即 nums[i] = i）。因而，就能通过索引映射对应的值，起到与字典等价的作用。

遍历中，第一次遇到数字 x 时，将其交换至索引 x 处；而当第二次遇到数字 xx 时，一定有 nums[x] = x ，此时即可得到一组重复数字。

实现

1、遍历+计数器

方式1 / int 型计数器

初始化一个长度为 n ，值为 0 的 int 数组作为计数器，在遍历 nums 的过程中以当前数字作为计数器的下标，将计数器下标对应的值 + 1 ，判断其值是否大等于 2 即可。

class Solution {
    public int findRepeatNumber(int[] nums) {
        // 数组长度
        int len = nums.length;
        // 初始化计数器
        int[] counter = new int[len];
        for (int i = 0; i < len; i++) {
            counter[i] = 0;
        }
        // 遍历
        for (int i = 0; i < len; i++) {
            // 将当前数字作为数组下标，填入计数器
            int index = nums[i];
            counter[index] += 1;
            // 判断当字符是否已经出现过
            if (counter[index] >= 2) {
                return nums[i];
            }
        }
        // 如果没有重复的数字，输出 -1
        return -1;
    }
}

方式2 / HashSet

借助 HashSet 的不可添加重复元素的性质，可以判断字符是否出现过。

class Solution {
    public int findRepeatNumber(int[] nums) {
        // 计数器
        Set<Integer> set = new HashSet<Integer>();
        // 重复的数字
        int repeat = -1;
        // 遍历
        for (int num : nums) {
            if (!set.add(num)) {
                repeat = num;
                break;
            }
        }
        return repeat;
    }
}

2、原地交换

class Solution {
    public int findRepeatNumber(int[] nums) {
        // 数组长度
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] == i) {
                // 无需交换
                continue;
            }
            if (nums[nums[i]] == nums[i]) {
                // 重复
                return nums[i];
            }
            // 交换索引为 i 和 nums[i] 的元素值
            int temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
        return -1;
    }
}