LeetCode 704-二分查找
题目描述：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
题目链接：二分查找
视频地址：二分法讲解
状态：之前就会了，相当于是巩固复习
思路：
- 将mid的值与target做比较，如果比target大，说明目标值在mid左边，此时修改right值，如果比target小，说明目标值在mid右边，修改left的值，依此类推。
- 注意二分法前提是有序数组。
关键点：左闭右开和左闭右闭区间的边界处理，以及right的取值问题
代码实现：
- 左闭右闭：
int search(vector<int>& nums, int target) {
auto left = nums.cbegin(), right = nums.cend() - 1;//使用迭代器顺便练习C++
while(left <= right) {
auto mid = left + (right - left) / 2;//防止溢出
if (*mid < target) {
left = mid + 1;
} else if (*mid > target) {
right = mid - 1;
} else {
return mid - nums.cbegin();
}
}
return -1;
}
- 左闭右开
int search(vector<int>& nums, int target) {
auto left = nums.cbegin(), right = nums.cend();//使用迭代器顺便练习C++
while(left < right) {
auto mid = left + (right - left) / 2;//防止溢出
if (*mid < target) {
left = mid + 1;
} else if (*mid > target) {
right = mid;
} else {
return mid - nums.cbegin();
}
}
return -1;
}
难点总结：
-
关于mid的取值方法问题
- mid = left + (right - left) / 2，因为（left + right）/ 2 有发生上溢可能，int 占用 4 字节，32 比特，数据范围为：
-2147483648 ~ 2147483647[-2^31 ~ 2^31-1]，那么对于两个都接近2147483647的数字而言，它们相加的结果将会溢出，变成负数。所以，为了避免溢出情况的发生，我们不采用这种写法。 - mid = left + (right - left) >> 2, 查阅资料采用右移运算速度比除法更快，因为出发涉及到浮点型数据，计算更慢。
- mid = left + (right - left) / 2，因为（left + right）/ 2 有发生上溢可能，int 占用 4 字节，32 比特，数据范围为：
-
关于 left 和 right 取值问题
- 当采用左闭右开的方法时，right = nums.size() - 1,此时right位置的值取不到，因此while循环的判断条件是left < right,而当目标值在mid左侧时，mid值此时也不等于target但是还需要保证mid - 1 在查找区间里，因此right = mid
- 当采用左闭右闭区间时，right = nums.size()，此时right位置在最后一个元素，可以取到，因此while循环的判断条件是left <= right,而当目标值在mid左侧时，mid值也不等于target，但是由于是闭区间，right = mid - 1时，也可以保证mid - 1在查找区间内。
27. 移除元素
题目描述： 给你一个数组 nums **和一个值 val，你需要 原地 移除所有数值等于 val **的元素，并返回移除后数组的新长度。
注意：
不要使用额外的数组空间，你必须仅使用
O(1)额外空间并 原地 修改输入数组元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
输入： nums = [3,2,2,3], val = 3
输出： 2, nums = [2,2]
解释： 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
题目链接：移除元素
思路：
方法一：暴力解法，遍历数组，遇到val，就将val后的元素依次向前移动一个位置。
方法二：快慢指针法：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
快指针（fast）：寻找新数组的元素，新数组就是不含有目标元素的数组
-
慢指针（slow）：用来存储新数组的元素，其指向新数组最后一个元素的后一个位置
用快指针去遍历数组，遇到val时，慢指针不动，继续向前，没有遇到val，slow = fast，两者都向前移动。
[图片上传失败...(image-31444b-1695196193111)]
方法三：相向双指针法，左右指针同时走，确保移动元素最少，但是元素相对位置发生变化.(方法二的优化)
代码实现：
快慢指针：
int removeElement(vector<int>& nums, int val) {
auto fast = nums.begin(), slow = nums.begin();
while(fast != nums.end()) {
if(*fast != val) {
*slow = *fast;
slow++;
}
fast++;
}
return slow - nums.begin();//slow在新数组最后一个元素的下一个位置，故不用+1
}
时间复杂度：O(n)，空间复杂度：O(1)
相向指针法：
int removeElement(vector<int>& nums, int val) {
int leftIndex = 0;
int rightIndex = nums.size() - 1;
while (leftIndex <= rightIndex) {
//注意是while循环，不是if
// 找左边等于val的元素
while (leftIndex <= rightIndex && nums[leftIndex] != val){
++leftIndex;
}
// 找右边不等于val的元素
while (leftIndex <= rightIndex && nums[rightIndex] == val) {
-- rightIndex;
}
// 将右边不等于val的元素覆盖左边等于val的元素
if (leftIndex < rightIndex) {
nums[leftIndex++] = nums[rightIndex--];//注意赋值完后元素移动
}
}
return leftIndex; // leftIndex一定指向了最终数组末尾的下一个元素
}
时间复杂度：O(n)，空间复杂度：O(1)
总结：
- 双指针法在数组链表里是很常见的方法，可能一下想不起来，多练多练多练！！！
