目錄
題目描述
思路
題解
復雜度
題目描述
找出陣列中重復的數字，
在一個長度為 n 的陣列 nums 里的所有數字都在 0～n-1 的范圍內，陣列中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次，請找出陣列中任意一個重復的數字，
示例 1：
輸入：
[2, 3, 1, 0, 2, 5, 3]
輸出：2 或 3
思路
遍歷中，第一次遇到數字 x 時，將其交換至索引 x 處；而當第二次遇到數字 x 時，一定有 nums[x] = x ，此時即可得到一組重復數字，
題解
class Solution {
public int findRepeatNumber(int[] nums) {
if (nums.length == 0) {
return -1;
}
for (int i = 0; i < nums.length; ++i) {
while (nums[i] != i) {
//發現重復元素
if (nums[i] == nums[nums[i]]) {
return nums[i];
}
//置換，將指標下的元素換到屬于他的索引處
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
return -1;
}
}復雜度
O(N)
O(1)
執行用時：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶
記憶體消耗：45.9 MB, 在所有 Java 提交中擊敗了90.47%的用戶
通過測驗用例：25 / 25
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/353304.html
標籤：其他
上一篇：程式員的演算法趣題Q56: 鬼腳圖中的橫線（思路2）
下一篇：線性列舉例題（二）