Day1二分查找，移除元素
By HQWQF 2023/12/13
笔记
704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
解法：使用二分查找来在一个有序的数组中找到指定元素的下标。
根据数据边界的不同，二分查找有两种写法。
区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。
两种写法的区别
- 区间left right 的初始值
- 循环条件
- 区间缩小时left right 的新值
左闭右闭[left, right]写法
class Solution
{
public:
int search(vector<int>& nums, int target)
{
int left = 0;
int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
// 当left==right，区间[left, right]依然有效，所以用 <=
//查找左闭右闭区间时，出现left==right的情况意味着只剩下了一个元素
while (left <= right)
{
int middle = left + ((right - left) / 2);
if (nums[middle] > target)
{
right = middle - 1; // target 在左区间，所以[left, middle - 1]
} else if (nums[middle] < target)
{
left = middle + 1; // target 在右区间，所以[middle + 1, right]
} else
{
return middle; // 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}
};
左闭右开[left, right) 写法
class Solution
{
public:
int search(vector<int>& nums, int target)
{
int left = 0;
int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
// 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
// 查找区间[left, right)时，nums[right]是不被考虑的
while (left < right)
{
int middle = left + ((right - left) >> 1);
if (nums[middle] > target)
{
right = middle; // target 在左区间，在[left, middle)中
//由于左闭右开的区间将nums[right] 排除在外，所以要将 right = middle，使nums[middle-1]参与到比较中
} else if (nums[middle] < target)
{
left = middle + 1; // target 在右区间，在[middle + 1, right)中
} else
{
return middle; // 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}
};
注释
- 二分查找的本质是不断缩小查找区间，二分查找的循环条件不成立意味着将区间缩小过头了都没有找到目标值
- 使用int middle = left + ((right - left) / 2);而不使用(left + right)/2是为了防止溢出
27. 移除元素
原地移除数组所有数值等于目标值的元素，并返回移除后数组的新长度。
解法：暴力法或快慢指针法
暴力法：
暴力遍历的方法会遍历所有元素，碰到目标值就将其后的元素全部前移一位，然后继续遍历
两层for循环，第一层for循环遍历数组元素 ，检测到目标值就进入第二层for循环更新数组。
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val)
{
int size = nums.size();
for (int i = 0; i < size; i++)
{
if (nums[i] == val)
{ // 发现需要移除的元素，就将数组集体向前移动一位
for (int j = i + 1; j < size; j++)
{
nums[j - 1] = nums[j];
}
i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
size--; // 此时数组的大小-1
}
}
return size;
}
};
快慢指针法
两个指针的含义
- 快指针：指向检测的元素
- 慢指针：指向要更新的数组元素
这个方法的本质是：在移位覆盖的同时进行目标值的检测，检测到目标值就略过这个元素，这个目标值元素就不会被向前复制移位，并在后续的循环中被其后的元素覆盖
// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val)
{
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++)
{
//普通的情况/if成立/没有遍历到目标值时，两个指针同步移动，
//如果该if不成立/检测到目标值时，慢速指针会慢一位，达到覆盖的效果
if (val != nums[fastIndex])
{
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;//上面这个if执行的次数=slowIndex的值=不等于目标值的元素，即删除目标值后的新长
}
};
相向双指针方法
另外还有相向双指针方法，这个方法可以确保移动最少元素，代价是会改变元素的顺序
// 时间复杂度：O(n)
// 空间复杂度：O(1)
int removeElement(vector<int>& nums, int val)
{
int leftIndex = 0;
int rightIndex = nums.size() - 1;
while (leftIndex <= rightIndex)
{
// 找左边等于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即是数组新长
//因为循环终止时，leftIndex = rightIndex+1，而rightIndex=nums.size()-1-等于目标值的元素个数
//所以leftIndex 就等于nums.size()-等于目标值的元素个数，即不等于目标值的元素个数