今日学习的视频和文章
- 代码随想录数组基础 复习基础知识
- 代码随想录 二分查找
- 代码随想录 移除元素
LeetCode704 二分查找
以前学二分查找的时候,真的一直搞不清楚怎么操作左边界和有边界,以及循环的终止条件是什么,总是自己慢慢调试出来,然后下一次又忘了。直到看见了 Carl 哥的讲解,让我有种醍醐灌顶的感觉。不仅是二分查找,写其他算法的时候,记得循环不变量原则也让我的思路清楚很多。
循环不变量原则,在 while 中每一次对边界的操作都要严格遵循区间的定义来操作,区间的定义就是循环不变量。
左闭右闭区间
- 初始化,区间的定义为左闭右闭区间,即
[l, r]
。
那么应该这样初始化:
int l = 0;
int r = nums.size() - 1;//r能取等号,所以应该是数组nums的最大下标
int mid = (l + r) / 2;
- 考虑边界条件,
l == r
时左闭右闭区间[l, r]
是合理的,所以while
语句的循环条件应为:
while (l <= r) {
/* 二分查找 */
}
- 若
target < nums[mid]
,即target
落在左边区间,nums[mid]
已经被查找过,所以调整右边界r
时,应该不包括mid
。
while (l <= r) {
if (target < nums[mid]) {
r = mid - 1;
}
/* ... */
}
- 若
nums[mid] < target
,即target
落在右边区间,nums[mid]
也已经被搜索过,所以调整左边界时,也不应该包括mid
。
while (l <= r) {
if (target < nums[mid]) {
r = mid - 1;
}
else if (nums[mid] < target) {
l = mid + 1;
}
}
-
若
nums == target
,即找到目标,直接返回mid
即可。 -
综合以上分析得到完整题解代码:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
int mid = (l + r) / 2;
while (l <= r) {
if (target < nums[mid]) {
r = mid - 1;
}
else if (nums[mid] < target) {
l = mid + 1;
}
else {
return mid;
}
mid = (l + r) / 2;
}
return -1;
}
左闭右开区间
- 初始化,左闭右开区间
[l, r)
。则r = nums.size()
。
int l = 0;
int r = nums.size();
int mid = (l + r) / 2;
- 考虑边界条件,对于左闭右开区间
[l, r)
而言,l == r
是不合理的,所以while
的循环条件应为l < r
。 - 调整左边界时,
mid
是被搜索过的,l
可以取等号,所以不应该包括mid
,即l = mid + 1
- 调整右边界时,
mid
被搜索过,r
不能取等号,正好将mid
赋值给r
,下一次循环的搜索范围正好不包括现在的mid
。如果r = mid - 1
,下一次循环的区间为[l, mid - 1)
,少包含了nums[mid - 1]
这个元素,显然逻辑是有问题的。
左闭右开区间的完整题解代码。
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size();
int mid = (l + r) / 2;
while (l < r) {
if (target < nums[mid]) {
r = mid;
}
else if (nums[mid] < target) {
l = mid + 1;
}
else {
return mid;
}
mid = (l + r) / 2;
}
return -1;
}
LeetCode27 移除元素
暴力解法
- 暴力解法,先移除元素,再让未移除的元素把空位补上。
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int del = 0;
for (int i = 0; i < n - del; i++) {
if (nums[i] == val) {
int j = i;
while (j + 1 < n) {
nums[j] = nums[j + 1];
j++;
}
del++;
i--;//这里要注意判断下一个元素是否等于 val,否则可能会漏掉 val 的元素
}
}
return n - del;
}
以上算法的时间复杂度为O(n^2)
双指针法(快慢指针法)
- 删除数组元素本质是用后面的元素覆盖前面的元素,让元素在空间上保持连续分布。那么,只需要判断哪个元素保留,哪个元素被覆盖,就可以在一次遍历中完成删除数组元素。
- 用
slow
指针指向要被覆盖的元素位置,用fast
指针表示当前遍历到的元素的位置。在遍历数组时,用nums[fast]
给nums[slow]
赋值。- 当
fast
指向要删除的元素时,fast
直接+ 1
而不用nums[fast]
给nums[slow]
赋值,此时fast
已经跳过了要被删除的元素。 - 然后,当 fast 指向不会被删除的元素时,用
nums[fast]
给nums[slow]
赋值,此时,被保留的元素覆盖了要被删除的元素的位置,完成了一个元素的删除,并且保持了元素在空间上的连续分布。
- 当
完整题解代码如下:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int fast = 0;
int slow = 0;
for (;fast < n; fast++) {
if (nums[fast] != val) {
nums[slow++] = nums[fast];
}
}
return n - fast + slow;
}
};