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

目录

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)