704.二分查找
题目:给定一个 n 个元素有序的(升序)整型数组和一个目标值 target,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
提示:
1.你可以假设nums中的所有元素是不重复的。
2.n将在[1,10000]之间。
3.nums的每个元素都将在[-9999,9999]之间。
解题:
思路:二分法可以使用的前提是:1.有序数组;2.数组中无重复元素。
在二分查找过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。
关键:边界条件,有两种:
一、左闭右闭[left,right]
- right=len(nums)-1
- while(left<=right),区间有效所以有=
- 先写>再写<:
- if(nums[middle]>target),target在[left,right]的左区间[left,middle-1],所以调整right=middle-1
- if(nums[middle]<target),[left=middle+1,right]
二、左闭右开[left,right)
- right=len(nums),定义target在的区间[left,right)
- while(left<right)
- if(nums[middle]>target):target在[left,middle),right=middle
- if(nums[middle]<target):target在[middle+1,right),left=middle+1
27.移除元素
题目:给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k,要通过此题,您需要执行以下操作:
- 更改 nums 数组,使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
- 返回 k。
解题:
思路:数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。
一、暴力解法
第一个while循环:遍历数组元素,找到要删除的元素后;
第二个for循环:更新数组,将该元素后面的数前移来覆盖,实现删除。
- if找到该节点,将后面的元素向前平移:for j in range(i+1, l):nums[j-1]=nums[j],平移完后l-=1
- 不是等于val的节点,i+=1
二、双指针法(快慢指针法)
快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组
慢指针:指向更新 新数组下标的位置
- 只用一个循环fast寻找不等于val的元素
- nums[slow]看作一个创建的新数组
- while fast<size,没有=,防止fast+=1后超出范围
- 不用else,无论是否等于val,fast都要+1
代码随想录的写法:
点击查看代码
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
# 快慢指针
fast = 0 # 快指针
slow = 0 # 慢指针
size = len(nums)
while fast < size: # 不加等于是因为,a = size 时,nums[a] 会越界
# slow 用来收集不等于 val 的值,如果 fast 对应值不等于 val,则把它与 slow 替换
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
chatgpt的写法更清晰:
点击查看代码
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow=0
for fast in range(len(nums)):
if nums[fast]!=val:
nums[slow]=nums[fast]
slow+=1
return slow
- 使用while需要手动fast+1,使用for就不需要。
- 想查看新数组长度,返回slow;想查看新数组,返回nums[:slow]