?
題目描述
在一個長度為 n 的數組里的所有數字都在 0 到 n-1 的范圍內。數組中某些數字是重復的，但不知道有幾個數字是重復的，也不知道每個數字重復幾次。請找出數組中任意一個重復的數字。
Input:
{2, 3, 1, 0, 2, 5}Output:
2 思路
給出了長度為n且數組內的數字的范圍是0-n，0-n的范圍恰好是這個數組的索引的范圍。思路是遍歷整個數組，把值為j的元素放到索引為j的位置上，如果整個數組沒有重復，那么在放置的過程中就不會發生沖突。
{3,0,2,1}
{0,1,2,3} 如果至少有一個元素發生了至少一次沖突，那么置換完畢后的數組的長度肯定小于原有數組的長度。
{3,0,2,2}
{0,2,3} 實現
這種需要置換的，肯定把置換的方法寫出來
public static void swap(int[]arr,int i,int j){/*** 把數組arr里位置i j的元素交換位置*/int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
我的第一版是這樣的，看起來好像沒啥問題。遍歷整個數組，然后把arr[i]位置的元素和arr[arr[i]]位置的元素交換。
public static boolean isDuplicate(int[] arr){int length = arr.length;for(int i=0; i<=length-1; i++){if(arr[i] == arr[arr[i]])return true;else {swap(arr, i, arr[i]);}}return false;}
我拿[3,1,0,2]這個數組測試的時候，返回的是true，這顯然是不對的。調試之后發現在i=1即循環一次后，數組變成了{3,1,2,0}，返回true。返回的條件是arr[1] == arr[arr[1]]。到這里我就看到我這個算法的問題了，我的算法只有在原始數組是完全亂序的前提下才會返回正確的結果，也即我的算法是判斷一個數組是否完全亂序。因為{3,1,2,0}中的1處在了正確的位置，所以會導致提前退出。
錯誤的原因是我沒有考慮到一個數組的arr[i]==i的情況下，也會出現上述的交換沖突。
public static boolean isDuplicate2(int[] arr){int length = arr.length;for(int i=0; i<=length-1; i++){if(arr[i] == arr[arr[i]] && arr[i] != i)return true;else {swap(arr, i, arr[i]);}}return false;}
?
?
?
)
)
