題目描述

在⼀個⻓度為 n 的數組⾥的所有數字都在 0 到n-1 的範圍內。 數組中某些數字是重複的，但不知
道有⼏個數字是重複的。也不知道每個數字重複⼏次。請找出數組中第⼀個重複的數字。 例如，如果輸⼊⻓度為 7 的數組 [2,3,1,0,2,5,3] ，那麼對應的輸出是第⼀個重複的數字 2 。沒有重複的數字
返回 -1 。

示例1

輸⼊
[ 2, 3, 1, 0, 2, 5, 3 ]

返回值
2

思路及解答

借用Set

⾸先可能想到的做法，就是藉助 set ，如果元素不存在 set 中，就將元素添加進去，如果 set
中包含該元素，就返回該元素即可。如果⼀直都沒有重複的，那麼最後返回 -1 。

public class Solution {
	public int duplicate(int[] numbers) {
		if (numbers != null) {
			Set<Integer> set = new HashSet<>();
			for (int i = 0; i < numbers.length; i++) {
				if (set.contains(numbers[i])) {
					return numbers[i];
				} else {
					set.add(numbers[i]);
				}
			}
		}
		return -1;
	}
}

• 時間複雜度：O(n) ，最差的情況可能遍歷完所有的元素
• 空間複雜度： O(n) ，最⼤需 要set ⼤⼩為 n

藉助數組

可以直接藉助數組，因為所有數字都在 0 到 n-1 的範圍內，⽤⼀個⼤⼩為 n 的數組，就可以對所有的數字進⾏統計個數，如果個數超過 1 ，那麼肯定是重複的數字，如果沒有重複的數字，則返回 -1 ；

public class Solution {
	public int duplicate(int[] numbers) {
		if (numbers != null) {
			int[] nums = new int[numbers.length];
			for (int i = 0; i < numbers.length; i++) {
				if (nums[numbers[i]] == 1) {
					return numbers[i];
				} else {
					nums[numbers[i]] = 1;
				}
			}
		}
		return -1;
	}
}

同樣這種做法的時間複雜度和空間複雜度都是 O(n) ,並沒有優化太多。

那麼有沒有空間複雜度為O(1) 的做法呢？

操作原數組（最優）

不借助額外的空間，那麼就只能操作原數組了。如果沒有重複的情況，那麼這些數字排序後，數字i 和數組下標i 應該是⼀⼀對應的。不會出現多個數字i 的情況。

基於這個原則，在遍歷數組的時候，將元素 i 調整到下標 i 的位置，如果下標i的位置已經有元
素，那麼説明衝突了，這個元素肯定是重複的，否則繼續調整後⾯的。如果沒有發現重複的數字，就返回 -1 。

public class Solution {
	public int duplicate(int[] numbers) {
		int i = 0;
		while(i < numbers.length) {
			if(numbers[i] == i) {
				i++;
				continue;
			}
			if(numbers[numbers[i]] == numbers[i]) return numbers[i];
			int tmp = numbers[i];
			numbers[i] = numbers[tmp];
			numbers[tmp] = tmp;
		}
		return -1;
	}
}

但是上⾯的做法，不適合求解多個重複數字的例⼦，因為調換的時候，很容易將後⾯的數字換到前⾯去，就會導致求解出來不是第⼀個重複的數字（可以⽤來求解任意的重複數字），可能是第2，3... 或者其他的重複數字。譬如： [6,3,2,0,2,5,0] 正確的解應該是 2 ，但是由於第⼀次把 6 和最後
的0 調換了位置，就會導致求解出來的值為 0 。