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

2024-01-09 22:38:05

目录

27 移除元素

704 二分查找


27 移除元素

快指针遍历,慢指针记录?

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int l = 0,r = 0;
        for(;r < nums.size();r++){
            if(nums[r] == val){

            }else{
                nums[l++] = nums[r];
            }
        }
        return l;
    }
};

?时间复杂度O(logn)

空间复杂度O(1)

704 二分查找

左闭右闭

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

?时间复杂度O(logn)

空间复杂度O(1)

左闭右开

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

时间复杂度O(n)

空间复杂度O(1)

文章来源:https://blog.csdn.net/m0_72832574/article/details/135490190
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。