2023-11-29 二分查找和移除元素
数组理论基础，704. 二分查找，27. 移除元素
704. 二分查找：时间复杂度O(log n)
核心：注意使用二分法的区间！第一种[left,right]属于左闭右闭 left=0 right=x-1 while left==<=======right left=mid+1 right=mid-1 !
class Solution:
def search(self, nums: List[int], target: int) -> int:
left=0
right=len(nums)-1
while left<=right:
mid=left+(right-left)//2 # 是防止整数过大导致int溢出
if nums[mid]==target:
return mid
elif nums[mid]>target:
right=mid-1
else:
left=mid+1
return -1
第二种[left,right)属于左闭右开 left=0 right=x while left==<==right left=mid+1 right=mid
class Solution:
def search(self, nums: List[int], target: int) -> int:
left=0
right=len(nums)
while left<right:
mid=left+(right-left)//2 # 是防止整数过大导致int溢出 习惯使用/是真除法
if nums[mid]==target:
return mid
elif nums[mid]>target:
right=mid
else :
left=mid+1
return -1
需要注意的是：python中//才是整除，别与其他语言混乱了！
时间复杂度：O(log n)
拓展题
35. 搜索插入位置
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
# 使用左右指针
left,right=0,len(nums)-1
while(left<=right):
mid = left+(right-left)//2
if nums[mid]==target:
return mid
elif nums[mid]>target:
right=mid-1
elif nums[mid]<target:
left=mid+1
# 关键是 没找到的时候left往前一步了 so left = right
left=right
return left+1
34. 在排序数组中查找元素的第一个和最后一个位置
这道题有意思！利用二分法来寻找左右边界，需要一个临时的值接受每一次出现相等target
# 第一种方法：利用二分法，寻找出左右边界
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
# 核心问题：是寻找左右边界
left,right=0,len(nums)-1
# 定义左右边界问题
leftboundary = -2
rightboundary = -2
# 左边界
def find_left_bounary(left, right):
temp_result = -2 # 去接住最后一次位置
while left <= right:
mid = left + (right - left) // 2
if nums[mid] >= target: # 注意边界【自己画个图走一下了理解】
right = mid - 1
temp_result = mid
else:
left =mid + 1
return temp_result
# 有边界
def find_right_boundary(left, right):
temp_result = -2
while left <= right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1
temp_result = mid
else:
right =mid - 1
return temp_result
leftboundary = find_left_bounary(left,right)
rightboundary = find_right_boundary(left,right)
# 如果target不在其中 那么leftboundary和rightboundary一定为初始值的
if leftboundary == -2 or rightboundary == -2:
return [-1,-1]
if (rightboundary - leftboundary) >= 0:
return [leftboundary,rightboundary]
return [-1,-1]
# 第二种方法：使用二分法找到一个与target相等的值，然后使用左右指针寻找边界
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left, right = 0, len(nums) - 1
temp_index = -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
temp_index = mid
# 从找target的下标开始沿着左右寻找
left,right = mid, mid
break
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
if temp_index == -1:
return [-1, -1]
# 左右寻找边界
while left >= 0 and nums[left] == target:
left -= 1
while right <= len(nums) - 1 and nums[right] == target:
right += 1
return [left + 1, right - 1]
# 第三种方法：找到第一次出现的target的下标也就是左边界了，然后找到target+1的下标值，也就是右边界的下标值
def searchRange(self, nums: List[int], target: int) -> List[int]:
def left_margin():
left, right = 0, len(nums) - 1
temp_index = -2
while left <= right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid - 1
temp_index = mid
else:
left = mid + 1
return temp_index
# 找出target+1的位置，
def right_margin(target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
index_first = mid
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
left = right # 注意这个就好了
return left
left_index = left_margin()
print(left_index)
right_index = right_margin(target+1)
print(right_index)
if left_index == -2:
return [-1,-1]
elif nums[left_index] == target and nums[right_index] == target:
return [left_index, right_index]
else:
return [-1, -1]
27. 移除元素
第一想法结题：使用标志位，但是移动元素麻烦做不了！使用双指针来做，列举指针两端的各种可能！
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
# 使用快慢指针来做 列举四种的可能性
slow,fast=0,0
while fast<len(nums):
if nums[slow] == val and nums[fast]==val:
fast+=1
elif nums[slow] == val and nums[fast] !=val:
nums[slow],nums[fast] = nums[fast],nums[slow]
slow +=1
fast +=1
elif nums[slow] !=val and nums[fast] ==val:
slow +=1
elif nums[slow] !=val and nums[fast] !=val:
fast +=1
slow +=1
return slow
优化一下：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow,fast=0,0
while fast<len(nums):
if nums[fast]!=val:
nums[slow]=nums[fast] # 不用考虑移动后续的元素！只需要有效的前面元素而已
slow +=1
fast +=1
return slow
或者可以
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow=0
for fast in range(len(nums)):
if nums[fast]!=val:
nums[slow]=nums[fast]
slow+=1
return slow