1. 题目描述
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
2. 题目分析
- 此题考查的是面试者的沟通能力，在面试官给出此题时，要询问面试官允许的时间复杂度和空间复杂度
- 关于此题，有三种解法，对应着三种不同的时间空间复杂度：
排序： 时间: O(nlogn) 空间O(1) HashMap： 时间: O(n) 空间O(n) 根据题目信息，按数值和下标：时间:O(n) 空间: O(1)
- 排序的解法：进行快排，然后
nums[i] != i，返回nums[i]; - HashMap的解法：初次出现时
map.put(nums[i], 1);再一次出现时，直接返回nums[i] - 数值和下标的解法：从下标0开始，将num[i]放在下标为num[i]的位置，如果坐标num[i]的值已经是num[i]，则返回num[i];
例如：1 0 2 3 5 2 当前指针为0 1 != 0 所以将1和0交换 0 1 2 3 4 5 2 0 == 0 指针++ 1 == 1 指针++ 2 == 2 指针++ 3 == 3 指针++ 4 == 4 指针++ 5 == 5 指针++ 2 != 6，但是目前下标2已经有2了，所以2是重复的
3. 题目代码
3.1 HashMap解法
public int findRepeatNumber(int[] nums) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])) { return nums[i]; } else { map.put(nums[i], 1); } } return 0; }
3.2 数值与下标
public static int findRepeatNumber1(int[] nums) { int i = 0; while (i < nums.length) { if (nums[i] == i) { i++; continue; // } if (nums[i] == nums[nums[i]]) { return nums[i]; } // 这里需要注意，在进行交换时，一定要写nums[i] = nums[temp]; // 不能写成nums[nums[i]] = nums[i]; 因为在第二步时，我们的nums[i]已经被改变 int temp = nums[i]; nums[i] = nums[temp]; nums[temp] = temp; } // -1：未被查到有重复的 return -1; }
