這個題目是這樣的
給你一串數值，裡面會有一個數值是有重複的，把他找出來
然後這邊有幾個條件：
1. 假設陣列長度為n，數值的範圍就是1~n-1
2. 重複的數值不一定只重複一次
Sol:
這個題目我想最值觀就是用個set存出現過的數值，然後一個一個找吧
這樣時間複雜度就是O(n)，空間複雜度也是O(n)
或是把陣列排序，然後一個一個找，比對下一個數值是否含現在這個數值一樣
時間複雜度是O(nlogn)，空間複雜度就是O(1) 或 O(n) (如果不修改傳進來的陣列的話，就要複製一份，所以可能會是O(n))
當然這兩種解法都是比較容易想到的方法
個人覺得這兩種方法會比較常用到，思路要稍微記一下
不過這題比較特別一點，因為有一個特殊的條件
1. 假設陣列長度為n，數值的範圍就是1~n-1
因為有這個條件，所以可以利用index來解
第一種就是用binary search的方式
其實這個跟前面排序的時間複雜度一樣，只是就不必修改傳進來的陣列了
具體想法大概是這樣：
假設陣列長度為n，我們可以先取n/2來看
如果陣列中的數值有(n/2)個以上都大於n/2，代表重複的數值會在n/2+1~n之間，反之就會在1~n/2之間
如此用二分法一直做下去，就會找到重複的那個值
大概是這樣：
int findDuplicate(vector<int>& nums) {
int low = 1;
int high = nums.size() - 1;
while (low < high)
{
int mid = (low + high) / 2;
int count = 0;
for (int i = 0; i < nums.size(); ++i)
{
if (nums[i] <= mid)
{
++count;
}
}
if (count > mid) // 陣列中小於mid的值的數量較多，故答案的範圍在low~mid
{
high = mid;
}
else
{
low = mid + 1;
}
}
return low;
}
然後這邊我遇到一個問題...
如果把if (nums[i] <= mid)的條件改成nums[i] > mid，我好像就做不出來了
我也不知道為啥...，腦袋一時轉不太過來= ="
好吧我之後想想再來補充...
(待補充)
然後還有另一種解法，可以按照https://leetcode.com/problems/linked-list-cycle-ii/solution/
就是利用 陣列長度為n，數值的範圍就是1~n-1 這個條件
把陣列裡的index當成節點的位址，裡面的值當成next
不過我不是很推薦這個解法啦... 實在是有夠不直觀的= =
那這題就這樣了=ˇ=
看似簡單的題目還是有眾多特殊的解法啊~
留言列表
