代码随想录算法训练营第一天| 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)