服装网站建设的目的和意义,建一个网页,网站的页面布局是什么样的,建设公司网站多少钱目录 1、思路讲解#xff08;LC704#xff09;2、代码思路讲解#xff08;循环不变量#xff09;#xff08;1#xff09; 左闭右闭#xff08;2#xff09;左闭右开#xff08;3#xff09;总结#xff1a;左开右闭和左闭右开#xff08;4#xff09;复杂度分析 … 目录 1、思路讲解LC7042、代码思路讲解循环不变量1 左闭右闭2左闭右开3总结左开右闭和左闭右开4复杂度分析 3. 习题分析1LC35 搜索插入位置 easy 二分查找法变种问题思路代码 2LC34 在排序数组中查找元素的第一个和最后一个位置 medium有重复元素的情况思路1二分查找线性遍历思路2扩展二分查找 1、思路讲解LC704 LC704给定一个长度为 n n n的数组 nums 元素按从小到大的顺序排列且不重复。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素则返回-1。 暴力法思路 从 n u m s [ 0 ] nums[0] nums[0]开始遍历一遍time complexity O ( n ) O(n) O(n) 二分法思路 ☀️首先要保证原序列是排好顺序的 2、代码思路讲解循环不变量
伪代码
def func(nums , target) - int:# 初始化首元素、尾元素left 0right len(nums) - 1 or len(nums)# 循环while 满足左指针在右指针的左边:# 理论上 Python 的数字可以无限大取决于内存大小无须考虑大数越界问题m (i j) // 2 # 计算中点索引 mif nums[m] target:# 说明target在nums[m]的右侧移动leftelif nums[m] target:# 说明target在nums[m]的左侧else:return m # 找到目标元素返回其索引return -1 # 未找到目标元素返回 -1这里面有几个很容易出错的点会导致循环不收敛
while的循环条件是 l e f t r i g h t leftright leftright or l e f t r i g h t leftright leftright当nums[mid]target的时候应该是 l e f t m i d 1 left mid1 leftmid1 or l e f t m i d left mid leftmid当nums[mid]target的时候应该是 r i g h t m i d − 1 right mid - 1 rightmid−1 or r i g h t m i d right mid rightmid 这几个问题的答案是你定义的区间是什么样子的
1 左闭右闭
如果定义的区间是左闭右闭的情况 [ l e f t , r i g h t ] [left,right] [left,right]
while的循环条件是 l e f t r i g h t leftright leftright ⭐️最推荐的选择so easy 因为当 l e f t r i g h t leftright leftright 的时候 [ l e f t , r i g h t ] [left,right] [left,right]区间中仍然有一个元素所以仍然是合法的 当nums[mid]target的时候应该是 l e f t m i d 1 left mid1 leftmid1 因为当nums[mid]target的时候就证明了mid指向的值一定不是目标值所以left不应该指向mid而应该是mid1 当nums[mid]target的时候应该是 r i g h t m i d − 1 right mid - 1 rightmid−1 or r i g h t m i d right mid rightmid
def binary_search(nums: list[int], target: int) - int:二分查找双闭区间# 初始化双闭区间 [0, n-1] 即 i, j 分别指向数组首元素、尾元素i, j 0, len(nums) - 1# 循环当搜索区间为空时跳出当 i j 时为空while i j:# 理论上 Python 的数字可以无限大取决于内存大小无须考虑大数越界问题m (i j) // 2 # 计算中点索引 mif nums[m] target:i m 1 # 此情况说明 target 在区间 [m1, j] 中elif nums[m] target:j m - 1 # 此情况说明 target 在区间 [i, m-1] 中else:return m # 找到目标元素返回其索引return -1 # 未找到目标元素返回 -12左闭右开
如果定义的区间是左闭右开的情况 [ l e f t , r i g h t ) [left,right) [left,right)
while的循环条件是 l e f t r i g h t leftright leftright 因为当 l e f t r i g h t leftright leftright 的时候 [ l e f t r i g h t , r i g h t ) [leftright,right) [leftright,right)区间就会既有right又没有right这种情况显然是不合法的 当nums[mid]target的时候应该是 l e f t m i d 1 left mid1 leftmid1 因为当nums[mid]target的时候就证明了mid指向的值一定不是目标值所以left不应该指向mid而应该是mid1 当nums[mid]target的时候应该是 r i g h t m i d right mid rightmid 因为区间是 [ l e f t , r i g h t ) [left,right) [left,right)当mid的值不是目标值的时候区间应该是mid值前面的序列但是因为右区间是开区间所以可以直接将right指向mid。
def binary_search_lcro(nums: list[int], target: int) - int:二分查找左闭右开区间# 初始化左闭右开区间 [0, n) 即 i, j 分别指向数组首元素、尾元素1i, j 0, len(nums)# 循环当搜索区间为空时跳出当 i j 时为空while i j:m (i j) // 2 # 计算中点索引 mif nums[m] target:i m 1 # 此情况说明 target 在区间 [m1, j) 中elif nums[m] target:j m # 此情况说明 target 在区间 [i, m) 中else:return m # 找到目标元素返回其索引return -1 # 未找到目标元素返回 -13总结左开右闭和左闭右开 4复杂度分析
时间复杂度 O ( l o g n ) O(logn) O(logn) 每次循环区间减少一半因此循环次数是 O ( l o g n ) O(logn) O(logn) 空间复杂度 O ( 1 ) O(1) O(1)没用使用数组啥的
3. 习题分析
1LC35 搜索插入位置 easy 二分查找法变种问题 LC35给定一个长度为 n n n的数组 nums 元素按从小到大的顺序排列且不重复。给一个元素target想要插入到nums中并保持有序性。如果数组中存在target就将targat插入到左侧如果不存在将target插入到按顺序插入的位置返回索引。 思路
⭐️思考 Q1 当数组中有target的时候插入点的索引是否就是返回值 回答 yep当查找到原数组有target值时新的target要放在老的target的左侧也就是说新的target代替了老的target的位置也就是插入点的索引就是新插入的target的索引 Q2 当数组不存在target的时候新插入点是哪个元素的索引
代码
def binary_search_insertion_simple(nums: list[int], target: int) - int:二分查找插入点无重复元素闭区间i, j 0, len(nums) - 1 # 初始化双闭区间 [0, n-1]while i j:m (i j) // 2 # 计算中点索引 mif nums[m] target:i m 1 # target 在区间 [m1, j] 中elif nums[m] target:j m - 1 # target 在区间 [i, m-1] 中else:return m # 找到 target 返回插入点 m# 未找到 target 返回插入点 ireturn i2LC34 在排序数组中查找元素的第一个和最后一个位置 medium有重复元素的情况 给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 思路1二分查找线性遍历
1️⃣ 执行二分查找得到任意一个 target 的索引 2️⃣从找到的这个索引开始分别向左和向右遍历找到start和end指针
class Solution:def searchRange(self, nums: List[int], target: int) - List[int]:if nums is None or len(nums) 0:return [-1,-1]# 先用二分查找法找到target# 双闭区间有重复元素left 0right len(nums) - 1flag 0while left right:mid left (right - left) // 2if target nums[mid]: # 应该删除前半部分的元素left mid 1elif target nums[mid]: # 应该删除后半部分的元素right mid - 1else: # 当找到其中一个目标值之后分别向前和向后遍历找到起始和终止位置flag 1start midend midwhile start 0 and nums[start] target:start - 1while end len(nums)-1 and nums[end] target:end 1breakif flag 1:return [start1,end-1]else:return [-1,-1]时间复杂度 O ( n ) O(n) O(n)数组中存在很多重复的 target 时该方法效率很低。
思路2扩展二分查找
1️⃣查找左边界
查找到任意一个target左边界 s t a r t start start必定在 [ l e f t , m i d − 1 ] [left,mid-1] [left,mid−1]中所以可以将 r i g h t m i d − 1 rightmid-1 rightmid−1缩小区间重新搜索一个新的target新的target必定在源target的左侧因为想要最左侧target的索引所以和LC704是一样的最后返回的是 s t a r t m i d startmid startmid
2️⃣查找右边界
class Solution:def searchRange(self, nums: List[int], target: int) - List[int]:if nums is None or len(nums) 0:return [-1,-1]# 扩展二分查找法查找target时候使用二分查找法确定边界的时候仍然使用二分查找法# 先用二分查找法找到左边界# 双闭区间有重复元素left 0right len(nums) - 1start -1while left right:mid left (right - left) // 2if target nums[mid]: # 应该删除前半部分的元素left mid 1elif target nums[mid]: # 应该删除后半部分的元素right mid - 1else: # 当找到其中一个目标值之后# 左边界start应该在[left,mid]之间right mid - 1start mid# 再用二分查找法找到右边界left 0right len(nums) - 1end -1while left right:mid left (right - left) // 2if target nums[mid]: # 应该删除前半部分的元素left mid 1elif target nums[mid]: # 应该删除后半部分的元素right mid - 1else: # 当找到其中一个目标值之后# 右边界end应该在[mid,right]之间left mid 1end mid return [start,end] 时间复杂度 O ( l o g N ) O(logN) O(logN)
