704.二分查找
题目链接：https://leetcode.cn/problems/binary-search/
文档讲解：https://programmercarl.com/0704.二分查找.html
视频讲解：https://www.bilibili.com/video/BV1fA4y1o715
左闭右开
- 时间复杂度 O(logn)
- 空间复杂度 O(1)
class Solution {
public:
int search(vector<int>& nums, int target) {
int low = 0, high = nums.size();
while(low < high) {
int mid = low + ((high - low) >> 1);
if (nums[mid] == target) return mid;
else if (nums[mid] < target) low = mid + 1;
else high = mid;
}
return -1;
}
};
左闭右闭
- 时间复杂度 O(logn)
- 空间复杂度 O(1)
第一遍写的时候循环条件写成while(low < high), 因为自己比较习惯写前闭后开的区间
这里要写while(low <= high) 因为low=high是有意义的，就像这样[1, 1]那么显然1在区间内
而如果是前闭后开的区间[1, 1)，1不在区间内，所以while(low < high)，这是很自然的嘛
class Solution {
public:
int search(vector<int>& nums, int target) {
int low = 0, high = nums.size() - 1;
while(low <= high) {
int mid = low + ((high - low) >> 1);
if (nums[mid] == target) return mid;
else if (nums[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
};
27.移除元素
题目链接：https://leetcode.cn/problems/remove-element/
文章讲解：https://programmercarl.com/0027.移除元素.html
视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP
暴力解法
- 时间复杂度 O(n2)
- 空间复杂度 O(1)
每次看到题目第一反应都是用暴力解，这道题的用暴力解很容易想到，唯一需要注意的就是，有连续的目标值出现时
一定要注意千万不要跳过了
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
for(int i = 0; i < nums.size(); ++i) {
if (nums[i] == val) {
for(int j = i; j < nums.size() - 1; ++j)
nums[j] = nums[j + 1];
nums.pop_back();
--i; // 每次处理完重复元素后，新元素填充到了i的位置，但是下一次循环开始i的值加1，那么新添加到i位置的元素被跳过了，所以--i；
}
}
return nums.size();
}
};
双指针法
- 时间复杂度 O(n)
- 空间复杂度 O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0;
while(slow < nums.size() && nums[slow] != val) ++slow;
int fast = slow + 1;
while(fast < nums.size()) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
};