找到升序的整数数组nums中与target相等的数字,并返回下标,如果没有则返回-1
二分法前提:有序数组,无重复元素
意味着可以取到right,即可以取到区间最右侧的值
定义right元素的时候,注意right=nums.size()-1? 可以取到
代码
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;
// int mid = left + ((right - left)/2);
int mid = left + ((right - left)>>1);
if(nums[mid]<target){
left = mid + 1;
}
else if(nums[mid]>target){
right = mid - 1;
}
else {
return mid;
}
}
return -1;
}
};
意味着不可以取到right,即不可以取到区间最右侧的值
定义right的时候,注意right=num.size()? ?取不到
代码
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;
// int mid = left + ((right - left)/2);
int mid = left + ((right - left) >> 1);
if(nums[mid]<target){
left = mid + 1;
}
else if(nums[mid]>target){
right = mid;
}
else {
return mid;}
}
return -1;
}
};
nums数组升序排列(无重复元素),返回数组中与target相等的元素的位置,若没有,则返回target在数组中应该插入的位置
插入的位置会有如下4种情况:
代码
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 - left) >> 1);
if(nums[mid] < target){
left = mid + 1;
}
else if(nums[mid] > target){
right = mid - 1;
}
else {
return mid;
}
}
// return left;
return right + 1 ;
//不可以返回mid,mid是一个局部变量,只在while循环里面有用
}
};
注意最终return的不可以是mid,因为mid是一个局部变量,只在while循环里面有效
代码
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
//左闭右开
int left = 0;
int right = nums.size();
while(left < right){
int mid = left + ((right - left) >> 1);
if(nums[mid] < target){
left = mid + 1;
}
else if(nums[mid] > target){
right = mid;
}
else {
return mid;
}
}
// return left;
return right; //与左闭右闭不同的是,左闭右开取不到右边界值,所以数字会插入在这个位置的
}
};
循环遍历整个数组,比较数组的每个元素与target的大小关系
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
//暴力解法
for(int i = 0;i<nums.size();i++){
if(nums[i] >= target){
return i;
}
}
return nums.size();
}
};
找出非递减排列的整数数组nums中? 与target相等的元素的开始位置和结束位置
如果不存在与target相等的元素,返回[-1,-1]
寻找target在数组里的左右边界,有如下三种情况:
代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int rightboard = getrightboard(nums, target);
int leftboard = getleftboard(nums, target);
if(rightboard == -2 || leftboard == -2){
return {-1,-1};
}
if(rightboard - leftboard > 1){
return {leftboard + 1, rightboard - 1};
}
return {-1, -1};
}
private:
int getrightboard(vector<int>& nums, int target){
int left = 0;
int right = nums.size() - 1;
int rightboard = -2;
while(left <= right){
int mid = left + ((right - left) >> 1);
if(nums[mid]>target){
right = mid - 1;
}
else{
left = mid + 1;
rightboard = left;
}
}
return rightboard;
}
int getleftboard(vector<int>& nums, int target){
int left = 0;
int right = nums.size() - 1;
int leftboard = -2;
while(left <= right){
int mid = left + ((right - left) >> 1);
if(nums[mid] >= target){
right = mid - 1;
leftboard = right;
}
else{
left = mid + 1;
}
}
return leftboard;
}
};
原地移除数组中所有数值等于val的元素,返回新的数组长度
一层是循环遍历数组的每个元素,另一层是比较更新数组
代码
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for(int i = 0;i < size;i++){
if(nums[i] == val){
for(int j = i + 1;j < size;j++){
nums[j - 1] = nums[j];
}
i--;//在nums[i]==val的情况下,元素都向前移了一位
size--;//因为元素向前移动一位,所以长度减1
}
}
return size;
}
};
fast快指针 nums[fast]与val比较? ?寻找新数组里面的元素(!=val)
slow新数组的下标
代码
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0;
for(int fast = 0;fast < nums.size();fast++){
if(nums[fast] != val){
nums[slow] = nums[fast];
slow ++;
}
}
return slow;
}
};