文章目錄
- 題目描述
- 代碼實作
題目描述
在一個長度為 n 的陣列 nums 里的所有數字都在 0～n-1 的范圍內，陣列中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次，請找出陣列中任意一個重復的數字，
輸入：
[2, 3, 1, 0, 2, 5, 3]
輸出：2 或 3
限制：
2 <= n <= 100000
代碼實作
如果下標 i 存盤的是 j，下標 j 中存盤的還是 j，則說明 j 重復出現，
int findRepeatNumber(vector<int>& nums){
for(int i=0; i < nums.size(); i++){
while(nums[i] != i){ // 下標i中存盤的不是i，而是j
int temp = nums[i];
if(temp == nums[temp]){ // 下標j中存盤的是j
return temp; // throw repeat number
}
else{ // 下標j中存盤的也不是j
swap(nums[i], nums[temp]);
// 交換下標j和下標i中的值，讓下標j中是j
}
}
}
return -1; // find't repeat number
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/275060.html
標籤：其他