代码随想录算法训练营Day 01| 704.二分查找、35.搜索插入位置、27.移除元素
文章目录
- 代码随想录算法训练营Day 01| 704.二分查找、35.搜索插入位置、27.移除元素
- 704. 二分查找
- 一、二分法—左闭右开
- 二、二分法——左闭右闭
- 三、本题总结
- 35. 搜索插入位置
- 一、二分法—左闭右开
- 二、二分法——左闭右闭
- 三、本题总结
- 27. 移除元素
- 一、快慢指针
- 二、优化双指针 - 左右指针
- 三、暴力解法
- 三、本题总结
704. 二分查找
题目链接
一、二分法—左闭右开
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
#左闭右开
left = 0
right = len(nums) #注意此处
while(left<right): #注意此处
mid = (left+right)/2
if nums[mid]<target:
left = mid +1
elif nums[mid]>target:
right = mid #注意此处
else:
return mid
return -1
二、二分法——左闭右闭
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
# 左闭右闭
left = 0
right = len(nums)-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
三、本题总结
注意本题的区间划分，坚持循环不变量。若为左闭右闭，则while循环的等号成立，且在更新右指针时，注意更新的范围，若 right = mid，则范围中又包含了mid，就不对了。反之，在左闭右开时，若right = mid-1 那么mid-1则会被忽略在范围外。
35. 搜索插入位置
题目链接
一、二分法—左闭右开
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
#左闭右开
left = 0
right = len(nums)
while(left<right):
mid = (left+right)/2
if nums[mid]<target:
left = mid +1
elif nums[mid]>target:
right = mid
else:
return mid
return left #或者return right
在最后一步时 left= right-1，那么mid = left<target,下个步骤left=right结束循环，left=right更新为插入的位置
二、二分法——左闭右闭
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left = 0
right = len(nums)-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 left #或者return right+1
在到最后一步时，left=right，那mid=left=right，因此下个步骤，循环结束，left>right,left更新为插入的位置，或right更新为最接近target且比target该插入位置-1的位置
三、本题总结
本题相较上一题主要的差别是在最后跳出循环的return，只要想清楚循环最后一步时left和right指针的位置，最后return的什么结果就很容易得到了。
27. 移除元素
题目链接
一、快慢指针
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
slow = 0
for fast in range(len(nums)):
if(nums[fast]!=val):
nums[slow]=nums[fast]
slow += 1
return slow #注意此处
二、优化双指针 - 左右指针
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
l = len(nums) #左闭右开
i = 0
while i < l: #左闭右开
if nums[i] == val:
# 如果找到等于val的元素，则将其与最后一个元素交换，然后删除最后一个元素
nums[i], nums[l-1] = nums[l-1], nums[i]
# 减少数组长度
l -= 1
# 这里不增加i的值，因为交换后的新元素还没有被检查
else:
# 如果当前元素不等于val，则继续检查下一个元素
i += 1
return l
方法二避免了需要保留的元素的重复赋值操作。
三、暴力解法
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
# 暴力
i = 0
l = len(nums)
while(i<l):
if nums[i] == val:
for j in range(i+1, l):
nums[j-1] = nums[j]
l -=1
i -=1
i+=1
return l
三、本题总结
注意双指针分别指代的是什么，左右指针的地方注意左闭右开还是左闭右闭，以及循环条件。