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

?今日任务?

• ?数组理论基础
• ?704.二分查找
• ?27.移除元素

? 数组理论基础

??? 文章链接： 代码随想录

??? 数组是存放在连续内存空间上的相同类型数据的集合。?

• 数组的下标都是从0开始的。
• 数组在内存空间的地址是连续的。

?? 因为数组的在内存空间的地址是连续的，所以在删除或者增添元素的时候，就难免要移动其他元素的地址。数组的元素是不能删的，只能覆盖。

? 不同编程语言的内存管理是不一样的，在C++中二维数组是连续分布的。

??704.二分查找（折半查找）

?题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

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

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -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 middle = left + ((right-left) / 2);//防止溢出，等同于(left+right)/2
             if (nums[middle] > target) {
                 right = middle - 1; //target在左区间[left,middle-1]
             }else if(nums[middle] <target) {
                 left = middle + 1; //target在右区间[middle+1,right]
             }else{
                 return middle; //在数组中找到目标值，直接返回下标
             }
        }
        return -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 middle = left + ((right-left) >> 1);//防止溢出，等同于(left+right)/2
             if (nums[middle] > target) {
                 right = middle; //target在左区间[left,middle)
             }else if(nums[middle] <target) {
                 left = middle + 1; //target在右区间[middle+1,right)
             }else{
                 return middle; //在数组中找到目标值，直接返回下标
             }
        }
        return -1; //未找到目标值
    }
};

?

?

27.移除元素

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

视频讲解：数组中移除元素并不容易！ | LeetCode：27. 移除元素_哔哩哔哩_bilibili

给你一个数组 nums?和一个值 val，你需要 原地 移除所有数值等于?val?的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

可通过暴力求解和快慢指针求解,实质为vector中erase函数的过程。

【思路】：暴力求解使用两层for循环，时间复杂度为O(n^2)，空间复杂度为O(1)；快慢指针求解可在一个for循环内完成两个for循环工作，时间复杂度为O(n)，空间复杂度为O(1)。

暴力解法

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++){
            if (nums[i] == val) { //发现需要移除的元素就将数组集体向前移动一位
               for (int j = i + 1; j < size; j++){
                   nums[j-1] = nums[j];
               }
               i--; //因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
               size--; //此时数组的长度-1
            }
        }
        return size;
    }
};

双指针法

class Solution{
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; int fastIndex < nums.size(); fastIndex++) {
             if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
             }
        } 
        return slowIndex;
    }
};

刷题心得

因为刚备考完考研，对今天两个题目思想还是比较熟悉的，对快慢指针的使用有了更深的理解，也清楚了数组删除元素的本质其实是覆盖。

?

?

?