在一個長度為n的陣列里的所有數字都在0到n-1的范圍內， 陣列中某些數字是重復的，但不知道有幾個數字是重復的，也不知道每個數字重復幾次，請找出陣列中任意一個重復的數字， 例如，如果輸入長度為7的陣列{2,3,1,0,2,5,3}，那么對應的輸出是第一個重復的數字2，
陣列的長度為 n 且所有數字都在 0 到 n-1 的范圍內，我們可以將每次遇到的數進行"歸位"，當某個數發現自己的"位置"被相同的數占了，則出現重復，
掃描整個陣列，當掃描到下標為 i 的數字時，首先比較該數字（m）是否等于 i，如果是，則接著掃描下一個數字；如果不是，則拿 m 與第 m 個數比較，如果 m 與第 m 個數相等，則說明出現重復了；如果 m 與第 m 個數不相等，則將 m 與第 m 個數交換，將 m "歸位"，再重復比較交換的程序，直到發現重復的數
舉個栗子：
以陣列 {2,3,1,0,2,5,3} 為例
當 i = 0 時，nums[i] = 2 != i，判斷 nums[i] 不等于 nums[nums[i]]，交換 nums[i] 和 nums[nums[i]]，交換后陣列為：{1,3,2,0,2,5,3}
此時 i = 0，nums[i] = 1 != i，判斷 nums[i] 不等于 nums[nums[i]]，交換 nums[i] 和 nums[nums[i]]，交換后陣列為：{3,1,2,0,2,5,3}
此時 i = 0，nums[i] = 3 != i，判斷 nums[i] 不等于 nums[nums[i]]，交換 nums[i] 和 nums[nums[i]]，交換后陣列為：{0,1,2,3,2,5,3}
此時 i = 0，nums[i] = 0 = i，繼續下一組
當 i = 1，nums[i] = 1 = i，繼續下一組
當 i = 2，nums[i] = 2 = i，繼續下一組
當 i = 3，nums[i] = 3 = i，繼續下一組
當 i = 4，nums[i] = 2 != i，判斷 nums[i] 等于 nums[nums[i]]，出現重復，賦值回傳
function duplicate(numbers, duplication) { // write code here //這里要特別注意~找到任意重復的一個值并賦值到duplication[0] //函式回傳True/False if(numbers==null){ return false } for (let i=0;i<numbers.length;i++){ while(numbers[i]!=i){ while(numbers[i]==numbers[numbers[i]]){ duplication[0]=numbers[i] return true } let temp=numbers[i] numbers[i]=numbers[temp] numbers[temp]=temp } } return false }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/2143.html
標籤：其他
上一篇：字串---替換空格
下一篇：陣列---構建乘積陣列