当前位置：首页 > article >正文

[代码随想录算法01] 704. 二分查找、27. 移除元素、977有序数组的平方

article 2025/2/22 2:12:07

前言

数组相关的最常用的操作的就是二分，因为二分可以很明显的将O（N）的时间复杂度降到O(logN),所以在一些中等的题目里面，我们很容易看到进阶的操作里面有优化时间复杂度的做法。

下一个常见的操作就是双指针，双指针对于有序的数组处理问题就是一绝，他可以通过，两个指针的快慢不同，直接将O（N^2）的暴力枚举，直接降低成O（2N）,也就是两次遍历即可。

题目链接

1、LeetCode704.二分查找
2、LeetCode27.移除元素
3、LeetCode977.有序数组的平方

一、二分查找

思路：常见的二分总共有三种写法，对应的就是闭区间，左闭右开，开区间。见下代码

分别对应的while的条件是不一样的，在rangs库函数里面的实现也是不一样的，这个我们可以在C++20里面的文档里面查看，库函数的使用方法是直接使用rangs里的lower_bound函数就是二分，tips：笔面不建议直接使用库函数，因为因为这个题就是让咱写二分的实现思路，哈哈哈。

class Solution {
public:
//闭区间
    int search1(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1,mid=0;
        while(left<=right){
            mid=left+((right-left)>>1);
            if(nums[mid]<target)left=mid+1;
            else if(nums[mid]>target)right=mid-1;
            else return mid;
        }
        return -1;
    }
//左闭右开
    int search2(vector<int>& nums, int target) {
        int left=0,right=nums.size(),mid=0;
        while(left<right){
            mid=left+((right-left)>>1);
            if(nums[mid]<target)left=mid+1;
            else if(nums[mid]>target)right=mid;
            else return mid;
        }
        return -1;
    }
//开区间
    int search3(vector<int>& nums, int target) {
        int left=-1,right=nums.size(),mid=0;
        while(left+1<right){
            mid=left+((right-left)>>1);
            if(nums[mid]<target)left=mid;
            else if(nums[mid]>target)right=mid;
            else return mid;
        }
        return -1;
    }
//库函数
    int search(vector<int>& nums, int target) {
        auto i=ranges::lower_bound(nums,target)-nums.begin();
        if(nums[i]==target)return i;
        else return -1;
    }
};

二、移除元素

思路1：暴力枚举，内层循环移动后续元素的位置。

思路2：快慢指针，遇见不等于目标元素的慢的＋＋

思路3：库函数，直接erase(nums,val)元素即可。

class Solution {
public:
//暴力枚举
    int removeElement1(vector<int>& nums, int val) {
        int sz=nums.size();
        for(int i=0;i<sz;i++){
            if(nums[i]==val){
                for(int j=i+1;j<sz;j++){
                    nums[j-1]=nums[j];
                }
                i--,sz--;
            }
        }
        return sz;
    }
//快慢指针
    int removeElement2(vector<int>& nums, int val) {
        int slow=0;
        for(int x:nums){//这里的K相当于快指针遍历
            if(x!=val) nums[slow++]=x;
        }
        return slow;
    }
//库函数
    int removeElement(vector<int>& nums, int val) {
        erase(nums,val);
        return nums.size();
    }
};

三、有序数组的平方

思路：暴力解法，直接范围for相乘，然后sort一下就行。快排的时间复杂度高。

思路2：直接用双端的数进行比较，优化时间复杂度。优化成O（N）。

class Solution {
public:
//暴力解法
    vector<int> sortedSquares1(vector<int>& nums) {
        for(auto& it:nums){
            it*=it;
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
//双指针优化
    vector<int> sortedSquares(vector<int>& nums) {
        int n=nums.size();
        vector<int>res(n);
        int i=0,j=n-1;
        for(int p=n-1;p>=0;p--){
            int x=nums[i],y=nums[j];
            if(-x>y){
                res[p]=x*x;
                i++;
            }else{
                res[p]=y*y;
                j--;
            }
        }
        return res;
    }
};