代码随想录算法训练营第一天 | 704 二分查找、27 移除元素

��day1 记录代码随想录第一天

第一题 力扣704 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

题目链接：. - 力扣（LeetCode）

本题思路为二分查找法。

定义两个边界left和right，取一个中间指针mid=(left+right)/2，如果考虑到数据越界，可以使用另一个公式：mid=left+(right-left)/2，结果都是一样的。

然后判断mid元素与target的大小，如果相等则直接输出，如果mid元素小于rarget，则left=mid+1，再次进循环。

考虑跳出循环的条件，主要考虑left=right的情况，如果存在这种情况，则left=right=mid，当mid=target时，直接输出mid，当不等时，则一定会在if以后出现left>right，则跳出循环，输出-1，由此，说明left=right是有意义的，需要在循环内加以讨论。

//二分查找class Solution {public:    int search(vector& nums, int target) {        int left = 0, mid = 0, right = 0;        right = nums.size() - 1;        while (left  target) {                right = mid - 1;            } else if (nums[mid]   
//二分左闭右开class Solution {public:    int search(vector& nums, int target) {        int left = 0, mid = 0, right = 0;        right = nums.size();        while (left  target) {                right = mid;            } else if (nums[mid]  
第二题 力扣27 移除元素
 
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
 
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
 
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
 
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
 
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
 
你不需要考虑数组中超出新长度后面的元素
 
题目链接：. - 力扣（LeetCode）
 
本题有两种解法，暴力求解和双指针
 
首先尝试暴力求解：
 
所谓暴力求解，就是指遍历、枚举、穷举等等方法
 
第一次编写：
 
class Solution {public:    int removeElement(vector& nums, int val) {        int length = 0;        for (int i = 0; i  
编译出错，怀疑是内存溢出了。
 
于是修改代码，此处nums.size()重复使用了三次，考虑直接使用中间变量length来替代。
 
再思考使用length表示数组长度，于是每次循环只用遍历length长度的数组即可，当发现与val相同的元素时，将第i个元素后面的元素覆盖到前一位。此时后面所有的元素都前移一位，所以length应减一，同时由于第i个元素被覆盖了，相当于此刻的第i个元素没有遍历，但是循环还是在往下走，将i减一可以将循环重走这一步，至此应该可以达到效果。
 
代码如下：
 
//暴力求解class Solution {public:    int removeElement(vector& nums, int val) {        int length = nums.size();        for (int i = 0; i  
提交通过！
 
同时有个很有意思的地方是用时0ms，超过100%用户，虽然知道这可能是系统内部计算有问题，但是还是挺激励自己的，开心！
  
双指针法：
 
双指针法是指在遍历对象的过程中，不仅仅使用一个指针遍历，而使用两个指针同时遍历访问，依两个指针访问方向相同和相反分为快慢指针和对撞指针。
 
快慢指针解法：
  
定义一个快指针fast，一个慢指针slow，使用快指针遍历整个数组，慢指针遍历不含val元素的数组，每当快指针遍历一个非val元素，就将慢指针所指元素对应此时快指针所指元素，由于循环条件中只有快指针++，所以应设置慢指针++语句，而当快指针遍历到val元素时，不需要做任何操作，直接快指针遍历过去，此时慢指针没变，慢指针所指元素没变，即慢指针所指元素对应的数组忽略了此元素，达成要求！
 
代码如下：
 
//双指针法（快慢指针）class Solution {public:    int removeElement(vector& nums, int val) {        int slowIndex = 0, fastIndex = 0;        for (fastIndex = 0; fastIndex  
对撞指针解法：
 
定义一个左指针和一个右指针，分别从两边遍历，每次遍历中，当左指针先找到一个val，在从右指针反方向找一个非val，并将两个指针对应的元素互换，之后左指针右移，右指针左移。需要注意的是，在整个过程中，需要保证左指针在右指针的左边，否则为越界。
 
代码如下：
 
//双指针法（对撞指针）class Solution {public:    int removeElement(vector& nums, int val) {        int leftIndex = 0, rightIndex = 0;        rightIndex = nums.size() - 1;        while(leftIndex