之前做過這樣的題，，之前的題是可以修改陣列的，那么如果不可以修改陣列，我們如何來做這個題呢？
1.題目
給定一個長度為 n+1 的陣列nums，陣列中所有的數均在 1～n 的范圍內，其中 n≥1，
請找出陣列中任意一個重復的數，但不能修改輸入的陣列，
樣例
給定 nums = [2, 3, 5, 4, 3, 2, 6, 7]，
回傳 2 或 3，
思考題：如果只能使用 O(1) 的額外空間，該怎么做呢？
題目來自于這里，有興趣的可以做一下，
2.時間復雜度為O(nlogn)的解法
自己沒想出來，看一位大佬寫的題解，
2.1原理
該解法的原理就是抽屜原理與分治，
抽屜原理：n+1個蘋果放入到n個抽屜中，那么必定有一個抽屜至少有兩個蘋果
這道題我們可以理解為，有n+1個位置，我們要給這n+1個位置賦值，范圍是1~n，那么必定有一個數要有兩個位置，
我們可以對這些數進行分治（不是位置），在范圍1~n當中的數的個數加起來一定是n+1，必定大于n，我們接下去縮小這個范圍，當在這個范圍中的數的個數加起來大于這個范圍的長度，就說明這個范圍中一定存在重復的數，依次下去，直到范圍的長度縮到1，我們就找到了重復的數了，
2.2代碼
int duplicateInArray(vector<int>& nums) {
int n = nums.size() - 1;
int left = 1, right = n;
while(left < right) {
int s = 0;
int mid = (left + right) / 2;
for(int i = 0; i <= n; i++) {
if(nums[i] >= left && nums[i] <= mid)
s++;
}
if(s > mid - left + 1)
right = mid;
else
left = mid + 1;
}
return right;
}
3.時間復雜度為O(n)的解法
題解原地址，看完只能說，大佬不愧是大佬，膜拜，
3.1原理
在這里有一點前置的知識，談一下我看完他們后的看法吧
3.1.1 如何判斷一個鏈存在環
存在環，那么我們就有一個相遇的問題，讓一個快的指標和一個慢的指標去回圈，它們就會相遇，
所以在這里，我們讓快指標每一次走兩步，慢指標每一次走一步，如果有環存在，那么兩個指標一定會相遇，
3.1.2 快指標與慢指標相遇的地點以及起點的關系
借一下原地址大佬的圖
首先，快指標速度是慢指標的二倍，相同時間內，快指標的位移一定是慢指標的二倍，
慢指標在進入環后，走完一周之前，一定會與快指標相遇，
將上述兩個位移化簡得
b + (k - 2l)c = a
公式中k-2L一定是個整數，所以b + 整數倍的圈數 位置依然沒有變，我們可以讓k = 2L，這樣結果是不影響最終位置的，
要細討論的話是分為三種情況，與a 和 c的大小有關系，（此處就不討論了）
我們便可以得出一個結論 a = 變化后的b 即相遇的地點與環起點相距b
3.1.3 將知識與題目結合
我們可以將上述知識應用到本題當中，我們可以將陣列對應的數當作next值來處理，索引值當作值來處理，由抽屜原理得這個陣列一定存在環，
我們先從索引值為0的數開始，將陣列對應的值當作next，讓快指標移動兩格，慢指標移動一格，相遇的地點即P點，接下來我們再讓快指標移動到0，然后一格一格的移動直到兩個指標相遇，此時索引值就是那個重復的數字，
3.2代碼
int duplicateInArray(vector<int>& nums) {
int low = 0, fast = 0;
while(low == 0 || low != fast) {
low = nums[low];
fast = nums[nums[fast]];
}
fast = 0;
while(low != fast) {
low = nums[low];
fast = nums[fast];
}
return fast;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259660.html
標籤：其他
上一篇：部署gitlab-01