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

LeetCode 704 二分查找

题目链接 : LeetCode704

左闭右闭:

视频讲解: 手把手带你撕出正确的二分法

思路: 在循环条件中注明left<=right，即[left,right]

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int middle = (left+right)/2;
            if(nums[middle]>target) right=middle-1; //因为是一个闭区间，只能取middle内的数组空间，所以right取middle-1
            else if(nums[middle]<target) left=middle+1; //同上
            else if(nums[middle]==target) return middle;
        }
        return -1;
    }
};

左闭右开:

思路: 在循环条件中注明left<=right，即[left,right)

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(left<right){
            int middle = (left+right)/2;
            if(nums[middle]>target) right = middle; //在左闭右开区间中，right取不到middle，因为left<right
            else if(nums[middle]<target) left = middle+1; // left取middle+1是因为左闭
            else if(nums[middle]==target) return middle;
        }
         return -1;
    }
};

LeetCode 27 移除元素

题目链接 : LeetCode27

暴力破解:  时间复杂度为O(n²)

思路: 数组是一个空间连续的数据结构，如果要删除下标为i所在位置的数据，则要将i+1位置的数据填充到i位置处

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--;
                size--;
            }
        }
            return size;
    }
};

双指针实现: 时间复杂度为O(n)

思路: 通过设置两个指针，一个快指针一个慢指针，将快指针不与目标值相等的数存入到慢指针数组中，实现在同一个数组中的删除元素操作。

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

双指针优化: 时间复杂度O(n)

思路: 在双指针实现的算法中，我们找到了目标值后所有的目标值之后的数据都要往前面进一位。所以我们将数组最后一个空间的数据传到目标值所在的空间当中，这样我们就只需要进行一次数组转移即可实现目标元素移除。

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