代码随想录算法训练营：1/60

非科班学习算法day1 | LeetCode704: 二分查找，Leetcode27: 移除元素

---

介绍

包含LC的两道题目，还有相应概念的补充。

相关图解和更多版本：

代码随想录 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF

---

一、基础概念补充：

1.数组基础

       1）一个数组中所有元素类型相同

       2）数组在内存中的地址是连续存放的，所以删除数组中间的某一个元素，就要将后面的元素都向前移动去覆盖。

2.c++中的vector

        1）vector是STL中的一种容器，vector可以理解为单端数组，只在vector的尾部提供一个接口

        2）vector支持随机访问的迭代器

        3）vector支持动态拓展，所以相对于数组更优秀

        4）vector支持查询size和capacticy

        5）vector支持用 [ ] 或者at查询

3.时间复杂度

        时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数. 时间复杂度常用大O表述，不包括这个函数的低阶项和首项系数。(参考高等数学无穷小的概念就好)

几种常见的时间复杂度：

常数阶O(1)
对数阶O(logN)
线性阶O(n)
线性对数阶O(nlogN)
平方阶O(n^2)
立方阶O(n^3)
K次方阶O(n^k)
指数阶(2^n)

        基本操作产生的时间复杂度为常数阶，多个顺序结构的复杂度按照加法计算，多个嵌套循环的复杂度按照乘法计算，一般在计算时间复杂度时，按照最坏时间复杂度进行计算。

二、LeetCode题目

1.LeetCode704: 二分查找

题目解析

        作为一个没有学过算法，基础也薄弱的人（我），自然会想到可以遍历vector，检查数组元素是否等于被查找值。若相等，返回当前下标；否则直至循环结束，在循环体外设置指定返回值 ：-1

 C++代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        //循环遍历查找target
        for (int i = 0;i < nums.size();i++)
        {
            if(nums[i] == target)
            {
                return i;
            }
        }
        return -1;
    }
};

时间复杂度分析:进行了双层的循环嵌套，按照最坏复杂度为O(n^2)

优化思路

        借助于二分查找可以有效降低查找次数（对数阶O(logN)），但是二分查找代码实现阶段最重要的就是边界设置，这里采用的是左闭右开的区间设置。

有两个值要额外注意，首先是右边界--决定了循环条件的设置（while里面可否取等于号），其次是mid，调整区间之后（二分比对之后），要注意之后的区间是否包含了右边界，在整个循环过程中，要坚持一个不变量原则，就是区间形式不能变（左闭右开/左闭右闭）。

 调整之后C++代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        //定义循环不变量为左闭右开
        int left = 0;
        int right = nums.size();       //这里右端不包含，所以可以取数组长度
 
        //定义循环条件，进入循环
        //循环条件为单向不包含等号，因为左右区间端点必定不可以相等
        while(left < right)
        {
            //定义和target比较的中值的下标
            int mid = left + (right - left) / 2;
            
            //进入条件判断
            //中值偏大
            if(target < nums[mid])
            {
                //右区间减小
                right = mid;    //不需要调整，因为右区间端点不包含
            }
            //中值偏小
            else if(target > nums[mid])
            {
                left = mid + 1;     //需要调整，左区间为包含
            }
            //中值匹配，返回中值下标
            else
            {
                return mid;
            }
        }
 
        //不符合循环条件，返回-1
        return -1;
    }
};

无注释版本： 

class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        int left = 0;
        int right = nums.size();      
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(target < nums[mid])
            {
                right = mid;    
            }
            else if(target > nums[mid])
            {
                left = mid + 1;    
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
};

 时间复杂度分析:按照最坏复杂度为O(log n)

2.LeetCode27: 移除元素

题目解析

        在数组基础中描述过，数组是不可以直接删除中间元素的，必须要对后面的元素也进行操作。所以这里就借用基本的思路：遍历数组，寻找目标值，将目标值后的所有元素遍历，向前覆盖。

这种算法实现起来并不困难，需要注意的是：

        在后面的元素移动之后，我们要再次检查此处的元素是否是目标值，所以外层采用了while循环，然后控制了i的自加条件。

 C++代码如下： 

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //遍历数组，寻找nums中符合val的值，删除该值
        //遍历该值后的部分，依据数组内存规则，将其向前覆盖
 
        int size = nums.size();
        int i = 0;
 
        //这里采用外层while
        while(i < size)
        {
            if(nums[i] == val)
            {
                for(int j = i + 1; j < size; j++)
                {
                    //实行覆盖
                    nums[j-1] = nums[j];
                }
                //调整数组长度，相对减少一点遍历
                size--;
            }
            //这里才调整i，因为覆盖之后，要检查原位置的元素
            else
            {
                i++;
            }
        }
        return size;
    }
};

 时间复杂度分析:按照最坏复杂度为O(n^2) 

优化思路

        借助于双指针，这里采用的是快慢指针。主要的想法是：

                快慢指针同时指向数组的头部；

                移动快指针对数组进行遍历；

                比对快指针指向的结果和目标值；

                慢指针更新数组信息

        

        我的理解叫做慢指针就是因为，可能存在需要舍弃的值，这里的“慢”是相对快指针来说的，由于慢指针记录了新的数组的信息，所以最后返回慢指针也就代表了有效的数组长度（k），关于详细的图解可以参考：

代码随想录 (programmercarl.com)https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html#%E6%80%9D%E8%B7%AF

 调整之后C++代码如下：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //采用快慢指针的方法来解决
        //定义快指针来遍历数组
        int fast = 0;
 
        //定义慢指针调整数组
        int slow = 0;
 
        //移动快指针
        for(;fast < nums.size(); fast++)
        {
            if(nums[fast] != val)
            {
                //不等则不变
                nums[slow] = nums[fast];
                slow++;         //调整慢指针的位置
            }
        }
 
        //返回有效数组长度
        return slow;
    }
};

 时间复杂度分析:按照最坏复杂度为O(n) 

---

总结

打卡第一天也是养成写博客习惯的第一天，坚持！！！