首页 > 编程语言 >Day1算法刷题(数组板块)

Day1算法刷题(数组板块)

时间:2024-12-31 20:09:34浏览次数:1  
标签:target 元素 mid Day1 算法 数组 刷题

二分查找

注意事项

  • left<=right,等于不能漏掉,定位到同一个元素的时候也要判断和target是否相等
  • left=mid+1,right=mid-1而不能是mid,否则会死循环,比如nums={1,2},target=2,此时mid就会一直指向1。

补充:

  • 数组为有序数组,同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件
  • 此处对应的是左闭右闭区间,还有左闭右开区间的写法,主要就是遵循循环不变量规则。

移除元素

  • 思考了很久的原地删除操作,原来是用双指针来的。
  • 我想到同O(n)也可用差分解决,不过更麻烦还要O(n)的空间大小,显然不太行。

977. 有序数组的平方 - 力扣(LeetCode)

  • 暴力也可接受,但仍然双指针解决最佳

长度最小的子数组

  • 收缩窗口,维护最小数组应该用while而不是if,因为新来的元素可能一个顶几个。比如nums={1,1},target=3,新来的为3,就可以把前面的1,1都扔掉。

标签:target,元素,mid,Day1,算法,数组,刷题
From: https://www.cnblogs.com/shallowdream123/p/18644724

相关文章