在一個長度為 n 的陣列 nums 里的所有數字都在 0～n-1 的范圍內，陣列中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次，請找出陣列中任意一個重復的數字， 【示例 1】 輸入： [2, 3, 1, 0, 2, 5, 3] 輸出：2 或 3 【限制】 2 <= n <= 100000
【解題思路】
思路一：先將陣列排序，再遍歷，找出重復的數字，
利用C++內置的sort函式排序，該方法時間復雜度為O(nlogn)，空間復雜度為O(1)，
class Solution { public: int findRepeatNumber(vector<int>& nums) { sort(nums.begin(),nums.end()); for(int i=0;i<nums.size()-1;i++){ if(nums[i]==nums[i+1]) return nums[i]; } return -1; } };
思路二：利用hash表，從頭開始遍歷陣列，如果元素不在hash表中，則向表中添加一個新的鍵值對，如果元素在hash表中，則回傳該元素，該方法，時間復雜度為O(n)，空間復雜度為O(n)，
class Solution { public: int findRepeatNumber(vector<int>& nums) { unordered_map<int,int> bp; for(int i=0;i<nums.size();i++){ if(bp.find(nums[i])==bp.end()) bp.insert({nums[i],1}); else return nums[i]; } return -1; } };
思路三：有沒有一種時間復雜度為O(n)，空間復雜度為O(1)的演算法呢？
我們注意到陣列中的數字都在0到n-1中，如果這個陣列中沒有重復的數字，那么當陣列排序之后數字i將出現在下標為i的位置，但是，由于陣列中有重復的數字，有些位置可能存在多個數字，同時有些位置可能沒有數字，
現在讓我們重排這個陣列，依然從頭到尾一次掃描這個陣列中的每個數字，當掃描到下標為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}，此時第0個數字是1，仍然與它的下標不相等，繼續把它和下標為1的數字3交換，得到陣列{3,1,2,0,2,5,3}.接下來繼續交換第0個數字3和第3個數字0，得到陣列{0,1,2,3,2,5,3}，此時第0個數字的數值為0，接著掃描下一個數字，在接下來的幾個數字中，下標為1,2,3的三個數字分別為1,2,3，它們的下標和數值都分別相等，因此不需要做任何操作，接下來掃描到下標為4的數字2.由于它的數值與它的下標不相等，再比較它和下標為2的數字，注意到此時陣列中下標為2的數字也是2，也就是數字在下標為2和下標為4的兩個位置都出現了，因此找到一個重復的數字，
class Solution { public: int findRepeatNumber(vector<int>& nums) { for(int i=0; i < nums.size(); i++) { while(nums[i] != i) { if(nums[i] == nums[nums[i]]) return nums[i]; else swap(nums[i],nums[nums[i]]); } } return -1; } };
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/27616.html
標籤：其他
下一篇：字串----正則運算式的匹配