LeetCode刷题记：数组——二分查找

作者： 千石

支持：点赞、收藏、评论

欢迎各位在评论区交流

前言

本文内容来自我平时学习的一些积累，如有错误，还请指正

在题目实战部分，我将代码实现和代码解释设置在了解题思路的下方，方便各位作为参考刷题

一些话

本文内容来自我平时学习的一些积累，如有错误，还请指正

在题目实战部分，我将代码实现和代码解释设置在了解题思路的下方，方便各位作为参考刷题

题目练习步骤：

1. 给自己10分钟，读题并思考解题思路
2. 有了思路以后开始写代码，如果在上一步骤中没有思路则停止思考并且看该题题解
3. 在看懂题解（暂时没看懂也没关系）的思路后，背诵默写题解，直至能熟练写出来
4. 隔一段时间，再次尝试写这道题目

刷题

704. 二分查找 - 力扣（LeetCode）

给定一个 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]之间。

题解

这道题是经典的二分查找问题，因为数组是有序的，所以可以通过二分查找来寻找目标值。

具体实现方法是，每次查找数组中间的元素，判断是否等于目标值，如果是，直接返回该下标；如果不是，则根据大小关系缩小查找范围。如果中间元素小于目标值，则在右半部分继续查找；如果中间元素大于目标值，则在左半部分继续查找。重复以上步骤直到找到目标值或者查找范围缩小为0。

以下是Python的实现代码：

defsearch(nums, target):
left, right=0, len(nums) -1whileleft<=right:
mid= (left+right) //2ifnums[mid] ==target:
returnmidelifnums[mid] <target:
left=mid+1else:
right=mid-1return-1复制代码

在代码中，变量left和right表示当前查找范围的左右边界，初始化为数组的第一个元素和最后一个元素。每次查找时，首先计算中间元素的下标mid，然后根据mid所在位置与target的大小关系来更新left和right的值，直到找到目标值或者查找范围缩小为0。如果最终没找到目标值，返回-1即可。

该算法的时间复杂度是O(logn)，因为每次查找都将查找范围缩小一半，总共最多需要查找logn次。

27. 移除元素 - 力扣（LeetCode）

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

题解

这道题可以使用双指针法来解决，一个指针用于遍历整个数组，另一个指针用于指向需要修改的位置。具体步骤如下：

1. 定义一个指针 index，初始值为 0。
2. 遍历整个数组，如果当前元素不等于 val，就将其赋值到 index 指向的位置，然后将 index 加 1。
3. 遍历结束后，返回 index 的值即可。

defremoveElement(nums, val):
index=0fornuminnums:
ifnum!=val:
nums[index] =numindex+=1returnindex复制代码

977. 有序数组的平方 - 力扣（LeetCode）

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]

题解

这道题的解法也很简单，因为数组已经按照非递减顺序排序，所以我们可以使用双指针法，分别指向数组的头部和尾部，比较两个指针所指的元素的平方大小，将较大的那个元素平方加入结果数组的末尾，然后移动指针。

具体步骤如下：

1. 定义两个指针 left 和 right，分别指向数组的头部和尾部。
2. 定义一个结果数组 res，长度为原数组的长度。
3. 遍历整个数组，比较 left 和 right 指向的元素的平方大小，将较大的那个元素平方加入结果数组的末尾，然后移动指针。
4. 遍历结束后，将结果数组反转即可。

代码如下：

defsortedSquares(nums):
n=len(nums)
res= [0] *nleft, right=0, n-1foriinrange(n-1, -1, -1):
ifabs(nums[left]) >abs(nums[right]):
res[i] =nums[left] *nums[left]
left+=1else:
res[i] =nums[right] *nums[right]
right-=1returnres