- LeetCode 704. 二分查找
- LeetCode 27. 移除元素
704. 二分查找
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 1:
1 | 输入:nums = [-1,0,3,5,9,12], target = 9 |
示例 2:
1 | 输入:nums = [-1,0,3,5,9,12], target = 2 |
思路
使用二分法前提条件:
- 数组为有序数组
- 数组中无重复元素
边界问题
首先确定查找的时候是否包括数组左右两边的数字,通常分为以下2种:
左闭右闭
- 查找范围在
[left, right]
区间,初值left, right=0, len(nums) - 1
。 while (left <= right)
要使用<=
,因为左闭右闭时,left == right
是有意义的。if (nums[mid] > target)
right == mid - 1
,因为中间值大于target,那么接下来要查找的范围应该包含中间值左边的那个值,而right赋值为 mid - 1 时,查找范围刚好是[left, mid - 1]。
- 查找范围在
左闭右开
- 查找范围在
[left, right)
区间,初值left, right=0, len(nums)
。 while (left < right)
要使用<
,因为左闭右开时,left == right
没有意义。if (nums[mid] > target)
right == mid
,因为中间值大于target,那么接下来要查找的范围应该包含中间值左边的那个值,而 right 赋值为 mid 时,查找范围刚好是[left, mid - 1]。
- 查找范围在
值溢出问题
mid = left + ((right - left) >> 1)
与mid = (left + right) // 2
计算结果一致,但当 left 和 right 很大的时候,前者可以防止溢出问题(python中整数对象是变长对象,所以不存在溢出问题),此外位运算速度比除法快。
python代码
左闭右闭
1 | class Solution: |
左闭右开
1 | class Solution: |
27. 移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
1 | 输入:nums = [3,2,2,3], val = 3 |
示例 2:
1 | 输入:nums = [0,1,2,2,3,0,4,2], val = 2 |
思路
- 数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,要删除某个元素,后面的只能向前覆盖。
- 暴力法
- 双层循环
- 注意:Python 中
for i in range(length)
中,i每次从迭代器中取数,循环体中改变i的值并不能改变下一次for循环中取到的i值,可以参考这里。
- 注意:Python 中
- 双层循环
- 双指针(快慢指针法)
- 快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组。
- 慢指针:删除了目标值的新数组的下标,慢指针只有在快指针的值不为target的值时才移动。
python代码
暴力解法 - python调库
1 | class Solution: |
暴力解法 - 双循环
1 | class Solution: |
双指针法(快慢指针)
1 | class Solution: |
赏
感觉不错 支持一下
本文作者:
三水
最后更新: 2022年11月17日 10:49:09
本文链接: https://sanshui.findn.cn/post/d446fd47.html
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可,转载请注明出处!
最后更新: 2022年11月17日 10:49:09
本文链接: https://sanshui.findn.cn/post/d446fd47.html
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可,转载请注明出处!