立志重刷代码随想录60天冲冲冲!!——第一天
704. 二分查找
第一天,二分查找比较简单。需要注意开闭区间和取值范围
我全以全闭区间为例
全闭需要left <= right,且缩小范围时不包括mid
class Solution { public: int search(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while(left <= right){ int mid = (left + right) / 2; if(nums[mid] < target){ left = mid + 1; }else if(nums[mid] > target){ right = mid - 1; }else{ return mid; } } return -1; } };
35.搜索插入位置
class Solution { public: int searchInsert(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while(left <= right){ int mid = (left + right) / 2; if(target < nums[mid]){ right = mid - 1; }else if(target > nums[mid]){ left = mid + 1; }else{ return mid; } } return left; } };
34. 在排序数组中查找元素的第一个和最后一个位置
今日时间太晚了,代码暂时先不写了。大致上思路就是:找到第一个target和最后一个target
第一个target:还是简单二分,然后target == nums[mid]时,再次添加right = mid - 1
最后一个target:简单二分,然后target == nums[mid]时,再次添加left = mid + 1
具体代码希望周末有时间补上!
27. 移除元素
左指针,新数组更新的位置
右指针,新数组的元素
右指针!=val的时候,左指针才会+1
class Solution { public: int removeElement(vector<int>& nums, int val) { int left = 0; int right = 0; int len_nums = nums.size(); while(right < len_nums){ nums[left] = nums[right]; if(nums[right] != val){ left++; } right++; } return left; } };
代码随想录更新 文章被收录于专栏
冲冲冲冲冲冲!