博客內(nèi)容：
● 今日學(xué)習(xí)的文章鏈接脐往，或者視頻鏈接
● 自己看到題目的第一想法
● 看完代碼隨想錄之后的想法
● 自己實現(xiàn)過程中遇到哪些困難
● 今日收獲，記錄一下自己的學(xué)習(xí)時長
704. 二分查找
v1
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
left, right = 0, n - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
return mid
return -1
看完代碼隨想錄之后的想法
主要就是對區(qū)間的定義沒有理解清楚扳埂，在循環(huán)中沒有始終堅持根據(jù)查找區(qū)間的定義來做邊界處理业簿。
區(qū)間的定義就是不變量，那么在循環(huán)中堅持根據(jù)查找區(qū)間的定義來做邊界處理阳懂，就是循環(huán)不變量規(guī)則辖源。
根據(jù)兩種常見的區(qū)間定義，給出了兩種二分法的寫法希太，每一個邊界為什么這么處理克饶，都根據(jù)區(qū)間的定義做了詳細(xì)介紹。
兩個版本寫法
（版本一）左閉右閉區(qū)間
class Solution {
public int search(int[] nums, int target) {
// 避免當(dāng) target 小于nums[0] nums[nums.length - 1]時多次循環(huán)運算
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}
}
（版本二）左閉右開區(qū)間
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid;
}
return -1;
}
}
相關(guān)題目推薦
- 35.搜索插入位置(opens new window)
- 34.在排序數(shù)組中查找元素的第一個和最后一個位置(opens new window)
- 69.x 的平方根
- 367.有效的完全平方數(shù)
27. 移除元素
v1
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i, j = -1, 0
while j < len(nums) and i <= j:
if nums[j] == val:
while nums[j] == val:
j += 1
if j >= len(nums):
break
if j >= len(nums):
break
i += 1
nums[i] = nums[j]
j += 1
else:
i += 1
nums[i] = nums[j]
j += 1
return i + 1
看完代碼隨想錄之后的想法
解法1 快慢指針（保持相對順序不變）
// 時間復(fù)雜度：O(n)
// 空間復(fù)雜度：O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (val != nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};
解法2相向雙指針（基于元素順序可以改變的題目描述改變了元素相對位置誊辉，確保了移動最少元素）
/**
* 時間復(fù)雜度：O(n)
* 空間復(fù)雜度：O(1)
*/
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int leftIndex = 0;
int rightIndex = nums.size() - 1;
while (leftIndex <= rightIndex) {
// 找左邊等于val的元素
while (leftIndex <= rightIndex && nums[leftIndex] != val){
++leftIndex;
}
// 找右邊不等于val的元素
while (leftIndex <= rightIndex && nums[rightIndex] == val) {
-- rightIndex;
}
// 將右邊不等于val的元素覆蓋左邊等于val的元素
if (leftIndex < rightIndex) {
nums[leftIndex++] = nums[rightIndex--];
}
}
return leftIndex; // leftIndex一定指向了最終數(shù)組末尾的下一個元素
}
};
相關(guān)題目推薦
- 26.刪除排序數(shù)組中的重復(fù)項
- 283.移動零
- 844.比較含退格的字符串
- 977.有序數(shù)組的平方
