LeetCode資料結構_LeetCode287

 LeetCode287

要求找到給定的整數內存中重複的數字

二分查找:

時間複雜度：O(n log n)，其中n是索引的長度。每次二分查找都需要遍歷整個索引

空間複雜度：O(1)，只需要幾個額外的變量來保存狀態，不需要額外的存儲空間。

優點：時間複雜度為 O(n log n)，比線性時間複雜度要好。不需要額外的空間。

缺點：可能需要修改集群本身，破壞原始數據。

1.初始範圍設定：我們將搜索的範圍初始化為 [1, n-1]，其中 n 是備份的長度。因為根據問題描述，備份中的元素範圍是 [1, n]。

2.在每一步中計算中間值mid，並統計集群中小於等於mid的元素個數（記為count）。根據抽屜原理，如果沒有重複數字，count應該小於等於mid。如果count大於mid，說明重複數字一定在左半部分，否則在右半部分。

3.根據上一步的判斷，我們不斷調整搜索範圍，縮小範圍直到找到重複數字。

如果沒有重複數字，那麼每個倉庫中最多只有一個物體（即倉庫中的一個物體）元素），而如果倉庫中有兩個物體，那麼就說明至少有一個倉庫中放了兩個元素，那麼倉庫中存在重複數字。

因為我們在搜索重複數字的時候可以，將集群分割成不同的區間來進行二分查找，而根據抽屜原理，如果有n個抽屜，放入了n+1個物體，那麼至少有一個抽屜中放了兩個物體。

1.程式碼

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { public: int findDuplicate(vector<int>& nums) { int left = 1; // 最小可能的重複數字 int right = nums.size() - 1; // 最大可能的重複數字 while (left < right) { int mid = left + (right - left) / 2; // 計算中間值 int count = 0; // 統計數組中小於等於 mid 的元素個數 for (int num : nums) { if (num <= mid) { count++; } } // 根據抽屜原理判斷重複數字在左半部分還是右半部分 if (count > mid) { right = mid; } else { left = mid + 1; } } return left; } };

備註:

鴿籠原理(抽屜原理) 

10隻鴿子放進9個鴿籠，那麼一定有一個鴿籠放進了至少兩隻鴿子。 

其中一種簡單的表述法為

若有n個籠子和n+1隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少2隻鴿子。

把多於n個的物體放到n個抽屜裏，則至少有一個抽屜裏的東西不少於兩件。

Ex:

如果你家有四個人，卻僅有三個房間，那麼至少有一個房間要住兩個人以上。

你買了五樣東西共花了101元，那麼這五樣東西中，至少有一樣的價值超過二十元。

可以不用二分查找嗎？

可以使用存儲表來記錄已經遍歷過的數字，以及它們的出現次數。

快慢指針,龜兔演算法(Hare & Tortoise Algorithm):

時間複雜度：O(n)，其中n是吞吐量的長度。快指針每次走兩步，慢指針每次走一步，所以最壞的情況下需要遍歷整個集群。

空間複雜度：O(1)，只需要幾個額外的變量來保存狀態，不需要額外的存儲空間。

優點：時間複雜度為O(n)，線性時間複雜度效率高。不需要額外的空間。

缺點：可能需要修改集群本身，破壞原始數據。

2.程式碼

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: int findDuplicate(vector<int>& nums) { int slow = nums[0]; int fast = nums[0]; // 找到快慢指针相遇的點 do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); // 將慢指針重置到起點，遇到即為重複數字的位置 slow = nums[0]; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; } };

Step1.初始化：我們將快指針（兔子）和慢指針（烏龜）都置於數組的第一個元素，即索引為 0 處。

Step2.循環相遇：我們開始一個循環，每次迭代中，快指針向前移動兩步，慢指針向前移動一步，直到它們相遇。這個過程模擬了兔子和烏龜在環形賽道上的移動。如果存在重複數字，它們最終會在環內的某個位置相遇。

Step3.相遇點：一旦快慢指針相遇，我們停止循環，此時它們相遇在環內的某個點。

Step4.重新設置慢指針：將慢指針重置為數組的第一個元素，即索引為 0 處。
Step5.再次相遇：接下來，同時移動快慢指針，每次都向前移動一步。由於它們的速度差異，當它們再次相遇時，它們會在環的入口點相遇。這是因為在第一次相遇後，慢指針在環內多走了 k 步（環的長度），所以當它們再次相遇時，恰好在入口點。

Step6.返回結果：當快慢指針再次相遇時，它們相遇的位置就是重複數字的位置，即環的入口點。

哈希表(unordered_map):

時間複雜度：O(n)，n 是存儲的長度。一次分佈式來構建緩存表，存儲表的插入和查詢操作的平均時間複雜度為O(1)。

空間複雜度：O(n)，需要額外的存儲空間來存儲哈希表，最壞的情況下需要存儲所有不同的元素。

修改優點：易於實現，不需要原始數據。能夠處理大部分情況下的問題。

缺點：需要額外的空間來存儲哈希表，可能會佔用分區內存。

3.程式碼

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: int findDuplicate(vector<int>& nums) { std::unordered_map<int, int> freqMap; for (int num : nums) { if (freqMap.count(num)) { return num; // 找到重复数字 } freqMap[num] = 1; } return -1; } };

基於排序的解法

時間複雜度：依賴排序算法，通常為 O(n log n)。需要對集群進行排序，最好情況下可以達到 O(n log n) 的時間複雜度。

空間複雜度：O(1)，通常是原地排序，不需要額外的存儲空間。

如果不考慮額外空間的情況下，可以使用排序來解決

優點：時間複雜度依賴排序算法，一般為O(n log n)。不需要額外空間，可以原地排序。

缺點：可能會修改原始數組的順序，而不是原地算法。

此外，排序解法通常不是最優解，因為其他解法可以在 O(n) 時間內解決該問題。

4.程式碼

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include <vector> #include <algorithm> class Solution { public: int findDuplicate(std::vector<int>& nums) { std::sort(nums.begin(), nums.end()); for (int i = 1; i < nums.size(); ++i) { if (nums[i] == nums[i - 1]) { return nums[i]; } } return -1; // } };

如果對空間複雜度度問題有嚴格要求，可以考慮使用快慢指針解法。

如果要求就地算法(in-place algorithm)且數據范圍限制比較嚴格，二分查找解法可能是一個不錯的選擇。

備註:

就地算法(in-place algorithm):基本上不需要藉助額外的資料結構就能對輸入的資料進行變換的演算法，不滿足「原地」原則的演算法也被稱為非原地（not-in-place）演算法或異地（out-of-place）演算法。