随想录一刷·数组part1

数组part1"/>

随想录一刷·数组part1

文章目录

• 1. 二分查找题型
• 2. 移除元素题型

1. 二分查找题型

二分查找·传送门

class Solution {
public:int search(vector<int>& nums, int target) {// 在有序数组中查找第一时间想到二分查找int left = 0, right = nums.size() - 1; // 左闭右闭while(left <= right){int mid = left + (right - left) / 2; // 防止溢出if(nums[mid] < target){left = mid + 1;}else if(nums[mid] > target){right = mid - 1;}else if(nums[mid] == target){return mid;}}return -1;}
};

题目拓展：

1. 搜索插入位置

class Solution {
public:// 注意对于本题的理解int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size(); // 左闭右开// 搜索左侧边界while(left < right){int mid = left + (right - left) / 2;if(nums[mid] == target){// 收缩右侧边界right = mid;}else if(nums[mid] < target){left = mid + 1;}else if(nums[mid] > target){right = mid;}}return left;}
};

2. 在排序数组中查找元素的左右边界

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {// 搜索左右边界int left = searchLeft(nums, target);int right = searchRight(nums, target);return {left, right};}// 搜索左侧边界int searchLeft(vector<int>& nums, int target){int left = 0, right = nums.size() - 1; // 左闭右闭while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] == target){// 收缩右侧边界right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else if(nums[mid] > target){right = mid - 1;}}// 注意判断if(left >= nums.size() || nums[left] != target){return -1;}return left;}// 搜索右侧边界int searchRight(vector<int>& nums, int target){int left = 0, right = nums.size() - 1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] == target){// 收缩左侧边界left = mid + 1;}else if(nums[mid] < target){left = mid + 1;}else if(nums[mid] > target){right = mid - 1;}}if(right < 0 || nums[right] != target){return -1;}return right;}
};

2. 移除元素题型

移除元素·传送门

class Solution {
public:int removeElement(vector<int>& nums, int val) {// 定义快慢指针， fast在前面探路，遇到值不为val的元素就赋给slowint slow = 0, fast = 0;while(fast < nums.size()){if(nums[fast] != val){nums[slow] = nums[fast];slow++;}fast++;}return slow;}
};