字母大的最小字母(744)、两个数组间的距离值(1385)"/>
LeetCode之搜索插入位置(35)、x的平方根(69)、二分查找(704)、寻找比目标字母大的最小字母(744)、两个数组间的距离值(1385)
二分查找——[简单题]
- 1、搜索插入位置(35)
- 2、x的平方根(69)
- 3、二分查找(704)
- 4、寻找比目标字母大的最小字母(744)
- 5、两个数组间的距离值(1385)
1、搜索插入位置(35)
题目描述:
【简单题】
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
题目链接
思路分析
1、排序数组,查找,可以想到运用二分查找方法
2、又因为如果目标值不存在于数组中,返回它将会被按顺序插入位置.
- 考虑这个插入的位置 pos \textit{pos} pos,它成立的条件为:
nums [ p o s − 1 ] < target ≤ nums [ p o s ] \textit{nums}[pos-1]<\textit{target}\le \textit{nums}[pos] nums[pos−1]<target≤nums[pos]
其中 nums \textit{nums} nums代表排序数组。由于如果存在这个目标值,我们返回的索引也是 pos \textit{pos} pos,因此我们可以将两个条件合并得出最后的目标:「在一个有序数组中找第一个大于等于 target \textit{target} target的下标」。
3、目标就是不断用二分法逼近查找第一个大于等于 target \textit{target} target 的下标.
-
考虑特殊情况:
- 如果数组的长度为0,则返回0
- 如果数组的最后一个元素小于目标值,则返回数组的长度
-
二分法逼近目标值
class Solution:def searchInsert(self, nums: List[int], target: int) -> int:left,right=0,len(nums)while left<right:mid=left+(right-left)//2#返回中间位置的下标,判断并进行下一次二分;这样算可以防止right+left可能会溢出的问题,解决时间超时的问题if nums[mid]<target:left = mid+1else:right = midreturn left
-
时间复杂度: O ( log n ) O(\log n) O(logn),其中 n n n 为数组的长度。
-
空间复杂度: O ( 1 ) O(1) O(1),我们只需要常数空间存放若干变量。
2、x的平方根(69)
题目描述:
【简单题】
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
题目链接
思路分析
方法:二分查找
1、由于 x 平方根的整数部分 ans \textit{ans} ans 是满足 k 2 ≤ x k^2 \leq x k2≤x的最大k 值,因此我们可以对k 进行二分查找,从而得到答案。
2、查找范围?
\quad \quad 一个数的平方根肯定不会超过它自己,不过直觉还告诉我们,一个数的平方根最多不会超过它的一半,例如8 的平方根,8 的一半是 4, 4 2 = 16 > 8 4^2=16>8 42=16>8 如果这个数越大越是如此,解不等式
( a 2 ) 2 ≥ a (\frac a2)^2\geq a (2a)2≥a得 a ≥ 4 a\geq 4 a≥4或 a ≤ 0 a\leq 0 a≤0,因此,一个数的平方根最多不会超过它的一半的特例是0,1,2,3,其平方根分别为0,1,1,1。
因此我们可设置
- 二分查找的下界为 0,【为了照顾到0】
- 二分查找的上界为这个数的一半再加1。【为了照顾到1,如果不加1的话,输入1将会出错】
class Solution:def mySqrt(self, x: int) -> int:l, r, ans = 0, x//2+1, -1while l <= r:mid = (l + r) // 2if mid * mid <= x:ans = midl = mid + 1else:r = mid - 1return ans
-
时间复杂度: O ( log x ) O(\log x) O(logx),即为二分查找需要的次数。
-
空间复杂度: O ( 1 ) O(1) O(1)。
3、二分查找(704)
题目描述:
【简单题】
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
题目链接
思路分析
二分查找模板
- 如果目标值等于中间元素,则找到目标值。
- 如果目标值较小,继续在左侧搜索。
- 如果目标值较大,则继续在右侧搜索。
搜索区间左闭右闭[left,right]
class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1while left <= right:mid = left + (right - left) // 2#返回中间位置的下标,判断并进行下一次二分;这样算可以防止right+left可能会溢出的问题,解决时间超时的问题if nums[mid] == target:return midif nums[mid]<target:left = mid + 1else:right = mid - 1return -1#执行结束没有找到返回-1
另一个通用模板:搜索区间左闭右开[left,right)
class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) while left < right:mid = left + (right - left) // 2#返回中间位置的下标,判断并进行下一次二分;这样算可以防止right+left可能会溢出的问题,解决时间超时的问题if nums[mid] == target:return midif nums[mid]<target:left = mid + 1else:right = mid return -1
-
时间复杂度: O ( log N ) \mathcal{O}(\log N) O(logN)。
-
空间复杂度: O ( 1 ) \mathcal{O}(1) O(1)。
4、寻找比目标字母大的最小字母(744)
题目描述:
【简单题】
给你一个排序后的字符列表 letters ,列表中只包含小写英文字母。另给出一个目标字母 target,请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时,字母是依序循环出现的。举个例子:
- 如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’],则答案返回 ‘a’
提示:
- letters长度范围在[2, 10000]区间内。
- letters 仅由小写字母组成,最少包含两个不同的字母。
- 目标字母target 是一个小写字母。
题目链接
思路分析
1、有序,寻找比目标字母大的最小字母,则可以利用二分查找算法解决此题。
2、在比较时,字母是依序循环出现的。因为若target大于letters里面的所有元素,那么退出循环时候left就会指向索引为len(letters)的位置,所以我们通过取余操作达到循环的效果。
【python3实现代码】
class Solution:def nextGreatestLetter(self, letters: List[str], target: str) -> str:left,right=0,len(letters)while left < right:mid=left+(right-left)//2if letters[mid]<=target:left=mid+1else:right=midreturn letters[left%len(letters)]
- 时间复杂度: O ( log N ) O(\log N) O(logN)。N 指的是 letters 的长度。
- 空间复杂度: O ( 1 ) O(1) O(1)。只使用了指针。
5、两个数组间的距离值(1385)
题目描述:
【简单题】
给你两个整数数组 arr1 , arr2 和一个整数 d ,请你返回两个数组之间的 距离值 。
「距离值」 定义为符合此距离要求的元素数目:对于元素 arr1[i] ,不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。
题目链接
思路分析
题解一:线性扫描
\quad \quad 按照题意模拟:对于 arr1
数组中的每一个元素 x i x_i xi ,枚举数组 arr2
中的每一个元素 y j y_j yj,如果对于每一个 y j y_j yj都有 ∣ x i − y j ∣ > d |x_i - y_j| > d ∣xi−yj∣>d,如果是,就将答案增加 1。
【代码实现】
class Solution:def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:count=0for x in arr1:if all(abs(x-y)>d for y in arr2):count+=1return count
- 时间复杂度: O ( m ∗ n ) O(m*n) O(m∗n),其中m,n分别为两数组的长度
- 空间复杂度: O ( 1 ) O(1) O(1)
题解二:二分查找
\quad \quad 对于arr1
数组中的每一个元素 x i x_i xi ,如果我们可以在arr2
数组中找到比它小的第一个元素和比它大的第一个元素,如果它们与 x i x_i xi 的绝对值距离大于d,那么arr2
数组中所有元素都满足条件,则 x i x_i xi符合距离要求,答案加1。
那么如何在arr2
数组中找与arr1
数组元素最接近的两个元素呢?——二分查找法
- 对
arr2
进行排序,然后对于 arr1 中的每个元素 x i x_i xi ,在 arr2 中进行二分查找,找到其在arr2
被顺序插入的位置即所在索引。【插入位置也需要分别讨论】- 如果插入索引为0即
arr2
数组中第一个位置,那么元素 x i x_i xi最接近元素仅有一个即arr2
数组中第一个元素。 - 如果插入索引为
arr2
数组长度,那么元素 x i x_i xi最接近元素仅有一个即arr2
数组中最后一个元素。 - 如果插入索引为其他值,那么元素 x i x_i xi最接近元素有两个即
arr2
数组中该插入的地方对应的元素及该索引前一个元素。
- 如果插入索引为0即
【代码实现】
class Solution:def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:arr2.sort()count=0for x in arr1:l,r=0,len(arr2)#寻找x应该插入到arr2数组哪个位置,l就是其所插入值while l<r:mid=l+(r-l)//2if arr2[mid]<x:l=mid+1else:r=midif l==0:# 如果插入位置索引为0即arr2数组中第一个位置if arr2[0]-x>d:# 求距离,可加一个绝对值符号,这样不会因大小的错误比较而导致结果错误count+=1elif l==len(arr2):# 如果插入位置为arr2长度if x-arr2[-1]>d:count+=1else:if abs(x-arr2[l])>d and abs(x-arr2[l-1])>d:count+=1return count
上述代码编写了一个程序实现待插入位置任务,还有一种简单的方法就是python中bisect模块可实现有序序列的插入和查找。
class Solution:def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:arr2.sort()count = 0for x in arr1:p = bisect.bisect_left(arr2, x)if p == len(arr2) or abs(x - arr2[p]) > d:if p == 0 or abs(x - arr2[p - 1]) > d:count += 1return count
题解三:排序+双指针
未完待续
更多推荐
LeetCode之搜索插入位置(35)、x的平方根(69)、二分查找(704)、寻找比目标字母大的最小字母(744)、两个数组间的距离值(1385)
发布评论