代码随想录算法训练营第一天|LeetCode704，35，34，27
LeetCode 704 二分查找
题目链接：https://leetcode.cn/problems/binary-search/
//第一次做还不知道二分中的左闭右开和左闭右闭指什么，于是写了很多边界条件辅助判断
class Solution {
public:
int search(vector<int> &nums, int target) {
int left = 0, right = nums.size() - 1;
//判断边界
if(target < nums[left] || target > nums[right]) return -1;
if(target == nums[left]) return 0;
if(target == nums[right]) return right;
//采用while循环找元素
while(left < right){
int mid = (left + right)/2;
//和mid下标所在元素做比较
if(nums[mid] < target) left = mid + 1;
else if(nums[mid] > target) right = mid;
else return mid;
}
return -1;
}
};
视频讲解链接：https://www.bilibili.com/video/BV1fA4y1o715
文章讲解链接：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
根据视频和文章讲解做出如下总结：
1.易错点：就像第一次做的时候，很难把握while循环中left是<还是<=right；target和mid下标对应元素做比较时，比如mid下标对应元素大于target时，right是等于mid还是等于mid-1？
2.首先明确区间的定义，主流写法是左闭右闭（[[left, right]]）和左闭右开（[left, right)）
3.第一种写法左闭右闭：根据区间定义，可得while循环中的判定条件是left <= right（起始right为num.size()-1）；假设nums[mid] > target，要去更新左区间的右边界，那这时候right值改为mid还是mid-1？答案是mid-1，因为采取的区间是左闭右闭，即我可以取到最右下标对应的元素值，如果选择mid，意味着算法可以取到mid下标对应的元素值，但已有nums[mid] > target，不能将不是自己搜索区间的值放在搜索区间里，所以选择mid不成立，应选择mid-1；假设nums[mid] < target，亦然，修正右区间的左边界，将left改为mid+1。
// 左闭右闭版本一
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
int mid = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
if (nums[mid] > target) {
right = mid - 1; // target 在左区间，所以[left, mid - 1]
} else if (nums[mid] < target) {
left = mid + 1; // target 在右区间，所以[mid + 1, right]
} else { // nums[mid] == target
return mid; // 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}
};
4.第二种写法左闭右开：根据区间定义，可得while循环中的判定条件是left < right（起始right为num.size()）；假设nums[mid] > target，要去更新左区间的右边界，那这时候right值改为mid还是mid-1？答案是mid，因为采取的区间是左闭右开，即我无法取到最右下标对应的值，如果选择mid-1，意味着算法无法取到mid-1下标对应的元素值，但已有nums[mid] > target，可以将mid作为不能被取到的值放在搜索区间里，所以选择mid；假设nums[mid] < target，亦然，修正右区间的左边界，将left改为mid+1。
// 左闭右闭版本二
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
int mid = left + ((right - left) >> 1);
if (nums[middle] > target) {
right = mid; // target 在左区间，在[left, mid)中
} else if (nums[mid] < target) {
left = mid + 1; // target 在右区间，在[mid + 1, right)中
} else { // nums[mid] == target
return mid; // 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}
};
LeetCode 35 搜索插入位置
题目链接：https://leetcode.cn/problems/search-insert-position/
//又是纯胡写，if else了一堆边界条件过得，因为还没有培养左闭右闭/左闭右开的意识
//O(logn)的时间复杂度
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
//判断边界：
if(target == nums[left] || target < nums[left]) return 0;
if(target == nums[right]) return right;
if(target > nums[right]) return right + 1;
int mid;
while(left < right){
mid = (left+right+1)/2;
if(nums[mid] == target) break;
else if(right == left+ 1 && target > nums[right]){mid++; break;}
else if(right == left+1 && nums[right]-nums[left] > target - nums[left]) break;
else if(nums[mid] < target) left = mid;
else if (nums[mid] > target) right = mid-1;
}
return mid;
}
};
文章讲解链接：https://programmercarl.com/0035.搜索插入位置.html#思路
根据文章讲解做出如下总结：
1.明确目标值target的四种情况：目标值在所有元素之前；目标值等于数组的某个元素；目标值插入数组中的位置；目标值在数组所有元素之后。
2.看到有序数组都可以联想一下能否使用二分查找，因为有序数组是二分查找的基础前提
//左闭右闭版本一
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
while (left <= right) { // 当left==right，区间[left, right]依然有效
int mid = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
if (nums[mid] > target) {
right = mid - 1; // target 在左区间，所以[left, mid - 1]
} else if (nums[mid] < target) {
left = mid + 1; // target 在右区间，所以[mid + 1, right]
} else { // nums[mid] == target
return mid;
}
}
// 分别处理如下四种情况
// 目标值在数组所有元素之前 [0, -1]
// 目标值等于数组中某一个元素 return mid;
// 目标值插入数组中的位置 [left, right]，return right + 1
// 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1
return right + 1; //return left; //因为跳出区间后left > right
}
};
//左闭右开版本二
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size(); // 定义target在左闭右开的区间里，[left, right) target
while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间
int mid = left + ((right - left) >> 1);
if (nums[mid] > target) {
right = mid; // target 在左区间，在[left, mid)中
} else if (nums[mid] < target) {
left = mid + 1; // target 在右区间，在 [mid + 1, right)中
} else { // nums[mid] == target
return mid; // 数组中找到目标值的情况，直接返回下标
}
}
// 分别处理如下四种情况
// 目标值在数组所有元素之前 [0,0)
// 目标值等于数组中某一个元素 return mid
// 目标值插入数组中的位置 [left, right) ，return right 即可
// 目标值在数组所有元素之后的情况 [left, right)，因为是右开区间，所以 return right
return right; //return left; //因为跳出区间后，left >= right
}
};
LeetCode 34 在排序数组中查找元素的第一个和最后一个位置
题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
//这个领会到了一点，是按照左闭右开写的，不过私以为这种题目更适合双指针
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.empty()) return{-1, -1};
int start = range(nums, target);
if(start == nums.size() || nums[start] != target) return{-1,-1};
int end = range(nums, target+1) -1;
return{start, end};
}
int range(vector<int>& nums, int target){
int left = 0, right = nums.size();
while(left < right){
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid + 1; // 范围缩小到 [mid+1, right)
else
right = mid; // 范围缩小到 [left, mid)
}
return left; //返回第一次遇到元素的位置
}
};
文章讲解链接：https://programmercarl.com/0034.在排序数组中查找元素的第一个和最后一个位置.html#思路
LeetCode 27 移除元素
题目链接：https://leetcode.cn/problems/remove-element/
//stl容器的暴力遍历
//erase这个库函数的时间复杂度是O(n)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
auto iter = nums.begin();
for(; iter != nums.end(); ){
if(*iter == val){
nums.erase(iter);
}
else{
++iter;
}
}
return nums.size();
}
};
视频讲解链接：https://www.bilibili.com/video/BV12A4y1Z7LP
文章讲解链接：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
根据视频讲解和文章讲解做出如下总结：
1.可以设立快慢指针，让快指针指向的元素覆盖掉慢指针指向的内容，这应该是双指针法的一种。
2.具体为快指针指向新数组所需要的元素，慢指针指向新数组的下标，把快指针指向的值赋给慢指针所在的位置
//快慢指针版本
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
size_t slowptr = 0;
for(size_t fastptr = 0; fastptr < nums.size(); fastptr ++){
//快指针获取元素，慢指针获取更新的位置
if(nums[fastptr] != val){
nums[slowptr++] = nums[fastptr];
}
}
return slowptr;
}
};
3.可以设立相向双指针，一个指针从头开始，一个指针从尾开始。
//相向双指针版本
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
//相向双指针，可以确保移动了最少的元素数量
int left = 0, right = nums.size() - 1;
//左闭右闭
while(left <= right){
//找左边等于val的元素
while(left <= right && nums[left] != val) ++left;
//找右边不等于val的元素
while(left <= right && nums[right] == val) --right;
//将右边不等于val的元素覆盖掉左边等于val的元素
if(left < right) nums[left++] = nums[right--];
}
//left一定指向了最终数组末尾的下一个元素
return left;
}
};