上次刷没刷完整,和李哥做字节的题感觉先前刷的题白刷了,故打算从头到尾完整走一遍。
二分法
1-1.二分查找
给定一个 n
个元素有序的(升序)整型数组 nums
和一个目标值 target
,写一个函数搜索 nums
中的 target
,如果目标值存在返回下标,否则返回 -1
。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示:
- 你可以假设 nums 中的所有元素是不重复的。
- n 将在 [1, 10000]之间。
- nums 的每个元素都将在 [-9999, 9999]之间
class Solution:
def search(self, nums: List[int], target: int) -> int:
l,r = 0,len(nums)-1
while l < r:
mid = l + r + 1 >> 1
if nums[mid] > target:
r = mid - 1
else:
l = mid
if nums[l] == target:
return l
return -1
RE了一次,原因是r的右侧初始化写成了len(nums)
1-2.搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n)
的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
- 1
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l,r = 0,len(nums)-1
while l> 1
if nums[mid] < target:
l = mid
else:
r = mid - 1
if nums[l] < target:
return l + 1
return l
一直WA,两个板子
第一个板子就是找第一个小于target值的位置,所以位置不能取到外面
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l,r = 0,len(nums)
while l> 1
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return l
这里和上面不一样,这里可以取到数组外面,我们找到的是第一个大于等于target的位置,所以可能取到len(nums)
总结:务必考虑清楚找到的是什么,然后敲定范围
1-3.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
你必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0
输出:[-1,-1]
提示:
- 0
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left,right = -1,-1
if len(nums) == 0:
return [-1,-1]
l,r = 0,len(nums) - 1
while l < r:
mid = l + r >> 1
if nums[mid] >= target:
r = mid
else:
l = mid + 1
if nums[l] == target:
left = l
l,r = 0,len(nums) - 1
while l < r:
mid = l + r + 1 >> 1
if nums[mid]
一次AC了,但存在两个编写时的问题
一是一开始left和right搞反了,上面是>=,所以是第一个大于等于target的位置,所以是左侧。相反下面的为右侧。
二是 nums = [], target = 0 RE了,特判一下
1-4.x 的平方根
给你一个非负整数 x
,计算并返回 x
的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5)
或者 x ** 0.5
。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
提示:
- 0
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0: return 0
if x > 1
if mid * mid > x:
r = mid - 1
else:
l = mid
return l
一次AC了,可能就是要考虑是大于x时才是不可能的完全不可能的情况,平方根乘起来必然
Original: https://www.cnblogs.com/ydssx7/p/16642223.html
Author: ydssx
Title: 代码随想录-数组篇
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/612578/
转载文章受原作者版权保护。转载请注明原作者出处!