立志用最少的代碼做最高效的表達

---

題目鏈接——>傳送門

---

找出數組中重復的數字。

在一個長度為 n 的數組 nums 里的所有數字都在 0～n-1 的范圍內。數組中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次。請找出數組中任意一個重復的數字。

示例 1：

輸入：
[2, 3, 1, 0, 2, 5, 3]
輸出：2 或 3

限制：

2 <= n <= 100000

---

解法一：排序

解決這個問題一個簡單辦法就是先把輸入的數組排序，從排序的數組中找出重復的數字是一件很容易的事情，只需從頭到尾掃描即可。

時間復雜度為O(nlogn)，空間復雜度O(1)

class Solution { public:int findRepeatNumber(vector<int>& nums) {int n = nums.size();sort(nums.begin(),nums.end());for(int i = 1; i < n; i++){if(nums[i-1] == nums[i])return nums[i];}return -1;} };

---

解法二：哈希表

構造一個長度為n的哈希表，遍歷數組，每掃描到一個數字，都判斷其是否在哈希表中存在，若不存在，則加入；若存在，則為重復數字。

時間復雜度為O(nlogn)，空間復雜度O(n)

代碼一：c++內置容器unordered_map實現（耗時較高）

class Solution { public:int findRepeatNumber(vector<int>& nums) {unordered_map<int,int>um;int k = 0;for(auto i : nums) {um[i]++;if(um[i] > 1) { k = i; break;}}return k;} };

代碼二：數組模擬哈希表（耗時低，因為數組效率高）

class Solution { public:int findRepeatNumber(vector<int>& nums) {int a[100005] = {0};int k = 0;for(auto i : nums) {a[i]++;if(a[i] > 1) { k = i; break;}}return k;} };

---

解法三：原地置換

現在讓我們重排這個數組。從頭到尾依次掃描這個數組中的每個數字。

當掃描到下標為i的數字時，首先比較這個數字（用m表示)是不是等于i。

如果是，則接著掃描下一個數字;如果不是，則再拿它和第m個數字進行比較。

如果它和第m個數字相等，就找到了一個重復的數字（該數字在下標為i和m的位置都出現了);如果它和第m個數字不相等，就把第i個數字和第m個數字交換，把m放到屬于它的位置。
接下來再重復這個比較、交換的過程，直到我們發現一個重復的數字。

以數組{2,3,1,0,2,5,3}為例來分析找到重復數字的步驟。數組的第0個數字(從0開始計數，和數組的下標保持一致)是2，與它的下標不相等，于是把它和下標為2的數字1交換。交換之后的數組是{1,3,2,0,2,5,3}。

此時第О個數字是1，仍然與它的下標不相等,繼續把它和下標為1的數字3交換，得到數組{3.1.2.0.2.5.3}。

接下來繼續交換第0個數字3和第3個數字0，得到數組{0.1.2.3.2.5.3}。此時第О個數字的數值為0，接著掃描下一個數字。

在接下來的幾個數字中，下標為1、2、3的3個數字分別為1、2、3，它們的下標和數值都分別相等，因此不需要執行任何操作。

接下來掃描到下標為4的數字2。由于它的數值與它的下標不相等，再比較它和下標為2的數字。

注意到此時數組中下標為2的數字也是2，也就是數字2在下標為2和下標為4的兩個位置都出現了,因此找到一個重復的數字。

時間復雜度為O(n)，空間復雜度O(1)

class Solution { public:int findRepeatNumber(vector<int>& nums) {int i = 0, len = nums.size();while(i < len) {if(nums[i] == i) {i++;continue;}if(nums[i] != nums[nums[i]]) {swap(nums[i], nums[nums[i]]);} else {return nums[i];}}return -1;} };

---

?????——朝著一個目標不斷做精深練習，不斷犯錯，不斷挑戰自己的極限，這種努力給你帶來的收獲絕對超出你的想象

總結

以上是生活随笔為你收集整理的【三种解法实现】剑指 Offer 03. 数组中重复的数字的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。