【剑指offer】- 数组中重复的数字 -48/67

1. 题目描述

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

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

2. 题目分析

1. 此题考查的是面试者的沟通能力，在面试官给出此题时，要询问面试官允许的时间复杂度和空间复杂度
2. 关于此题，有三种解法，对应着三种不同的时间空间复杂度：

排序：    时间: O(nlogn)  空间O(1)
HashMap： 时间: O(n) 空间O(n)
根据题目信息，按数值和下标：时间:O(n) 空间: O(1)

3. 排序的解法：进行快排，然后nums[i] != i，返回nums[i];
4. HashMap的解法：初次出现时map.put(nums[i], 1); 再一次出现时，直接返回nums[i]
5. 数值和下标的解法：从下标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;
	}