704 二分查找：
题目链接
解题思路：
暴力循环： 自己的思路
- 从左往右，遍历每个元素。
- 检查当前元素是否满足要求。
- 若满足要求则返回当前元素的下标。
时间复杂度：O(n)；
空间复杂度：O(n)；
二分查找：
- 题目给定的是一个升序的数组，即有序数组！
- 那么二分的前提是有序（或者具有某种特殊的性质！）。
- 故可以采用二分。
- 每次二分出来一个中间元素，然后将中间元素和
target进行一个比较。 - 若中间元素 <
target，说中间元素左边的元素均小于target所以左边的元素排除存在target的可能性。令l = mid+1；为什么加1呢？因为mid所指向的元素已经小于target了，所以可以直接指向下一个。 - 若中间元素 >=
target，说中间元素右边的元素均小于target所以右边的元素排除存在target的可能性。令r = mid。为什么是r = mid呢？因为此时比较条件是>=，所以r指向的元素必然是存在等于target的可能性的。
时间复杂度：O(log n)
空间复杂度：O(n)
实现代码：
暴力循环：
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
for (int i=0; i < n; i ++) {
if (nums[i] == target) {
return i;
}
}
return -1;
}
};
二分版本一：下面还有版本二，版本一、二的区别请稍后在题目总结里面查看！
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int l=0, r = n-1;
while (l < r)
{
int mid = (l + r) >> 1;
if (nums[mid] < target) l = mid + 1;
else r = mid;
}
if (nums[r] == target) return l;
else return -1;
}
};
二分版本二：下面还有版本二，版本一、二的区别请稍后在题目总结里面查看！
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
if (n == 1) {
if(nums[0] != target) return -1;
else return 0;
}
int l = -1, r = n;
while (l+1 != r)
{
int mid = l + r >> 1;
if (nums[mid] >= target) r= mid;
else l = mid;
}
if (nums[r] == target) return r;
else return -1;
}
};
错误解法：
无
题目总结：
二分版本一、二的区别：
27. 移除元素：
题目链接
解题思路：
暴力循环：自己的
- 外层循环负责遍历枚举每一个元素；
- 当遍历到值为
val的元素时，进入内层循环； - 内层循环，负责将当前值为
val的元素，后面的元素，依次往前覆盖。从而移除了所有满足条件的元素。
时间复杂度：n^2
空间复杂度：n
标记排序：自己的
- 观察题目的数据，元素值最大是100。
- 逐个遍历每个元素。检查当前枚举的元素是否为
val，若是的话，则记录数量。 - 并且将当前元素设置为
int_max； - 最后遍历完成后，进行一个排序即可！
- 然后返回 数组长度 - 记录的数量
时间复杂度：nlog(n)
空间复杂度：n
双指针：别人的
双指针的核心是用一层for循环做了两层for循环要做的事情。
想一想我们两层for循环分别做了什么事情。
外层for：枚举检查每个元素是否值为 val；
内层for：删除当前值为 val 的元素。
那么我们可以设置两个指针啊！
右指针：负责检查核对每一个元素是否值为 val；
左指针：负责更新数组。
但是题目规定了不准另外开辟一个数组。
但是我们可以在原有的数组上建立一个新数组啊！
左指针所指向的位置，即为新数组。
把右指针所指向的元素，如果值不等于 val，则将该元素赋值 给 左指针所指向的位置。那么最终左指针当前指向的元素，及其前面的元素都必然是没有值为val的。所以左指针此时指向最后一个位置，也代表着新数组的长度！
优化版本
时间复杂度：n
空间复杂度：n
实现代码：
暴力循环：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
for (int i=0; i < n; i ++) {
if (nums[i] == val) {
for (int j=i+1; j < n; j ++) {
nums[j-1] = nums[j];
}
i --; //因为下标i以后的数值都向前移动了一位，所以i也需要向前移动一位。
n --; //数组大小-1
}
}
return n;
}
};
标记排序：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int cnt=0;
for (int i=0; i < n; i ++) {
if (nums[i] == val) {
cnt ++;
nums[i] = INT_MAX;
}
}
sort(nums.begin(), nums.end());
return n - cnt;
}
};
双指针：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int l=0;
for (int r=0; r < n; r ++) {
if (nums[r] != val) {
nums[l] = nums[r];
l ++; //指向下一个位置，等待赋值。
}
}
return l;
}
};
双指针优化：
优化链接
错误解法：
1、暴力循环
错解一：
当删除了一个元素后，此时 i 和 j 所指向的元素也会发生变化，若删除后，不进行任何的操作，则会导致 i 所指向的新的元素被跳过，遗漏。
如何处理呢？
错解二：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int cnt=0;
for (int i=0; i < n; i ++) {
if (nums[i] == val) {
cnt ++;
for (int j=i+1; j < n; j ++) {
nums[j-1] = nums[j];
}
i --; //因为下标i以后的数值都向前移动了一位，所以i也需要向前移动一位。
}
}
return n - cnt;
}
};
题目总结：
快慢指针的思想：文章来源：https://www.toymoban.com/news/detail-581550.html
- 实际上就是将两重for循环，变为一重for循环，用两个变量分别替代两个for循环所做的事情即可！
- 优化的关键在于，敢于在原数组上进行操作，右指针已经遍历过的位置，必然是不重要的。利用右指针的元素值给左指针赋值，即为创建新元素。
- 记住，左右指针进行交互的条件是什么！当右指针指向的元素值不为 val 的时候，右指针赋值给左指针。
- 本来最初用双指针做的时候，想的是如何删除右指针所指向的元素，就是当右指针指向的元素等于 val 的时候该如何处理。实际上这时候应该反向处理，思考右指针指向的元素不等于 val 的时候如何处理。
- 这个思想就跟：一个东西，它有许多优点，但是你记不住那么多，但是他有一个缺点，所以你就只需要记住他的这一个缺点不就行了，不就可以区分他了吗？
双指针：
可以在原数组的基础上，不用额外开空间，构建一个新的数组，并且能够在原数组中筛选特定元素构成新数组。文章来源地址https://www.toymoban.com/news/detail-581550.html
到了这里，关于Leetcode 704.二分查找、27.移除元素的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
