Re: [閒聊] 每日LeetCode
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 540. Single Element in a Sorted Array
: 給你一個已排序整數陣列，裡面的所有數字都有恰好兩個，只有一個數字只有一個，
: 找出這個數字是什麼，限制時間複雜度：O(logn)且空間複雜度：O(1)。
: Example :
: Input: nums = [1,1,2,3,3,4,4,8,8]
: Output: 2
: Input: nums = [3,3,7,7,10,11,11]
: Output: 10
解題思路:
一樣用 binary search 維護左右邊界，
左邊界 l: 保證不是答案的最大值，初始為 -1，
右邊界 r: 可能是答案的最小值，初始為 size - 1。
由於 l 左邊保證不是答案，所以一定是偶數個數字，
戳到 mid 如果是奇數index (含自己左邊有偶數個數字)，只要跟左邊相鄰數字檢查，
戳到 mid 如果是偶數index (不含自己左邊有偶數個數字)，只要跟右邊相鄰數字檢查，
等到邊界 l + 1 == r 的時候 nums[r] 就是答案。
C++ code:
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int l = -1, r = nums.size() - 1;
while(l + 1 < r){
int mid = (l + r) / 2;
if(mid & 1){
if(nums[mid] == nums[mid - 1]) l = mid;
else r = mid;
}
else{
if(nums[mid] == nums[mid + 1]) l = mid + 1;
else r = mid;
}
}
return nums[r];
}
};
---
上面那是一年多前寫的捏，
今天早上是寫分治版本的二分搜，
我覺得一年多前的我好像比較強 :000
解題思路:
扣掉重複元素後往奇數個數字的那邊做搜尋。
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
return divide(nums, 0, nums.size() - 1);
}
int divide(vector<int> &nums, int l, int r){
if(l == r) return nums[l];
int mid = (l + r) / 2;
if((mid - l) % 2 == 0){ // 左邊奇數
if(nums[mid] == nums[mid - 1]){
return divide(nums, l, mid - 2);
}
else if(nums[mid] == nums[mid + 1]){
return divide(nums, mid + 2, r);
}
else return nums[mid];
}
else{ // 右邊奇數
if(nums[mid] == nums[mid - 1]){
return divide(nums, mid + 1, r);
}
else if(nums[mid] == nums[mid + 1]){
return divide(nums, l, mid - 1);
}
else return nums[mid];
}
}
};
---
話說 PTT 上的字型 1 跟 l 也太像了吧 :(
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1676957613.A.E3A.html
推
02/21 13:37,
2年前
, 1F
02/21 13:37, 1F
※ 編輯: idiont (140.113.229.216 臺灣), 02/21/2023 13:39:21
推
02/21 14:15,
2年前
, 2F
02/21 14:15, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 245 之 719 篇)：