● 今日学习的文章链接和视频链接
● 自己看到题目的第一想法
1. 704二分法：
方法一：
整个数组是 左闭右闭区间 [ ]
- left指针指向数组开始下标， right 指针指向数组最后下表nums.size()-1, mid为 (left+right) /2
- 循环条件 left<=right
- nums[mid] <target 右移left left = mid+1
nums[mid] > target 左移right right = mid-1
nums[mid] = target 返回 mid
找不到 返回 -1
方法二：
整个数组是 左闭右开区间 [ )
- left指针指向数组开始下标， right 指针指向数组最后下表nums.size(), mid为 (left+right) /2
- 循环条件 left< right
- nums[mid] <target 右移left left = mid+1
nums[mid] > target 左移right right = mid
nums[mid] = target 返回 mid
找不到 返回 -1
2.注意：区间边界问题
整个数组是 左闭右闭区间 [ ]
整个数组是 左闭右开区间 [ )
3.具体代码
方法一：
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size()-1;
while(left<=right){
int mid = (left+right)/2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] >target){
right = mid-1;
}else if(nums[mid]< target){
left = mid+1;
}else{
return mid;
}
}return -1;
}
};
方法二：
class Solution {
public:
int search(vector<int>& nums, int target) {
int left =0;
int right = nums.size();
while(left< right){
int mid = (left +right)/2;
if(nums[mid] < target){
left =mid+1;
}else if(nums[mid] > target){
right = mid;
}else{
return mid ;
}
}
return -1;
}
};
2. 27移除元素
思路
方法一：双指针
- 定义下标 快指针fast ， 慢指针slow
- 循环条件 fast <= nums.size()-1
- nums[fast] == val 则fast++;
nums[fast] != val 则 nums[slow] = nums[fast], slow++, fast++;
slow最终指向没有val值 数组最后一个元素的下标。
方法二：
4. 定义left =0 right =nums.size()-1
5. 循环条件 left<=right
6. 左边找到nums[left]==val 的下标
右边找到nums[right] !=val 的下标
交换 nums[left] =nums[right] left++; right–;
结果： return left;
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left =0;
int right = nums.size()-1;
while(left<=right){
while(left<=right && nums[left] != val){
left++;
}
while(left<=right && nums[right] == val){
right--;
}
if(left<=right){
nums[left] = nums[right];
left++;
right--;
}
}
return left;
}
};
注意
slow指：更新后 新数组下标
fast 指：寻找新数组的元素
代码
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow =0;
int fast =0;
for(fast = 0; fast <nums.size(); fast++){
if(nums[fast] != val){
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
};
