劍指 Offer —— 陣列中重複的數字
摘要：
陣列中的重複數字
題目描述
牛課網連結
長度為 n 的數組裡，所有數字都在 0 到 n-1 的範圍內。陣列中某些數字是重複的，但不知道有幾個數字是重複的。也不知道每個數字重複幾次。請找出陣列中任意一個重複的數字。 例如，如果輸入長度為 7 的陣列{2,3,...
陣列中的重複數字
題目描述
長度為 n 的數組裡，所有數字都在 0 到 n-1 的範圍內。陣列中某些數字是重複的，但不知道有幾個數字是重複的。也不知道每個數字重複幾次。請找出陣列中任意一個重複的數字。 例如，如果輸入長度為 7 的陣列{2,3,1,0,2,5,3}
，那麼對應的輸出是第一個重複的數字 2。
A 簡單實現思路
藉助外部陣列 b，原陣列中的數字記為外部陣列的下標，外部陣列的值來儲存這個數字出現的次數。原陣列中的數字都在 0 到 n-1 的範圍內，因此外部陣列 b 的長度為 n 即可。
public boolean duplicate(int[] numbers, int length, int[] duplication) {
if (numbers == null) {
return false;
}
int[] array = new int[length];
for (int i = 0; i < length; i++) {
if (array[numbers[i]] > 0) {
duplication[0] = numbers[i];
return true;
}
array[numbers[i]]++;
}
return false;
}
時間複雜度 O(n)，空間複雜度 O(n)
B 劍指 Offer 思路
如果陣列中沒有重複的數字，排序後第 i 個位置會存放值為 i 的數字。因為陣列中某些數字是重複的，在排序後，某個位置處會存放多個相同數字（邏輯上的，就相當於疊起來），有些位置就沒有數字。前者就是我們要找的數字。但是我們並不去排序，只是利用這種思想，把值為 i 的元素放到下標為 i 的位置。
具體來說，我們從前往後依次遍歷該陣列。當遍歷到下標 i 時，記該位置上的數字為 x，如果 x 等於 i，就跳過。如果 x 不等於 i，就判斷 x 應放位置處（即下標 x 處）的數字（計作 m）是否已經是 x 了，如果是就找到了一個重複的數字（迴圈結束）；如果 m 不等於 x，那麼就交換下標 i、x 的兩個數（保證把位置 i 處的 x 放置到正確的位置上），直到 x 等於 i。
/**
* 將值為 i 的元素調整到下標為 i 的位置，如果該位置上的數已經等於 i 了，就說明 i 已經重複了
* @param numbers
* @param length
* @param duplication
* @return
*/
public static boolean jz(int[] numbers, int length, int[] duplication) {
for (int i = 0; i < length; i++) {
//下標 i 處的數 numbers[i]，若不與下標 i 相等，就把 numbers[i] 放到下標 numbers[i] 處
while (numbers[i] != i) {
//在交換位置之前還要檢查下標 numbers[i] 處的數字是否已經是 numbers[i]，如果是就已經找到了重複的數字
if (numbers[numbers[i]] == numbers[i]) {
duplication[0] = numbers[i];
//注意這裡不是 break
return true;
}
//交換下標為 i、numbers[i] 兩個位置上的數字（保證值為 numbers[i] 的元素放到下標 numbers[i] 處）
swap(numbers, i, numbers[i]);
}
}
return false;
}
/**
* 交換下標為 i、j 的兩個數
* @param numbers
* @param i
* @param j
*/
public static void swap(int[] numbers, int i, int j) {
int swap = numbers[i];
numbers[i] = numbers[j];
numbers[j] = swap;
}