力扣——数组（一）

一、二分法（有序数组）

1、搜索等于target的元素

法一：

直接遍历

class Solution {
public:int search(vector<int>& nums, int target) {int i=0;for(i=0;i<nums.size();i++){if(nums[i]==target){return i;}}return -1;}
};

法二：

二分查找（前提：数组已经是升序排序）

1、设left、right、middle

2、让target和nums[middle]比较，分类讨论

3、移动左边界或右边界

class Solution{
public:
int search(vector<int>& nums, int target) {int left=0,right=nums.size()-1; //1 设置左、右、中间变量int middle=(left+right)/2while(left<=right){int middle=(left+right)/2;if(target<nums[middle]){  //2 target与中间值比较并分类讨论：比中间值大还是小还是相等right=middle-1;  //target偏小则right左移}else if(target>nums[middle]){left=middle+1; //target偏大则left右移}else{return middle; //相等则返回当前下标middle}}return -1;
}
};

注意：如果是[ ]，则

1、左右边界初始值：left=0，right=nums.size()-1

2、循环条件：while(left<=right) left==right时[left，right]仍有意义

3、移动边界：因为已经明确nums[middle]不等于target，所以应让left=middle+1，right=middle-1

如果是[ )，则

1、左右边界初始值：left=0，right=nums.size()

2、循环条件：while(left<right) left==right时[left，right)没有意义

3、移动边界：因为已经明确nums[middle]不等于target，所以应让left=middle+1，right=middle

2、搜索等于target的元素或target的插入位置

有序数组，可以使用二分法

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<=right){int middle=(left+right)/2;if(target==nums[middle]){return middle;}else if(target<nums[middle]){right=middle-1;}else{left=middle+1;}}return left; //找不到目标值则返回插入位置，经推算插入位置就是left}
};

注意：如果找不到等于target的值，则要考虑三种插入情况

插入在数组之前、数组之后、数组之中

举个最简单的例子来推算：比如[0]，left=right=middle=0

target=-100时，right左移，最终right=-1，left=0，而插入位置是0

target=100时，left右移，最终left=1，right=0，而插入位置是1

综上，猜测插入位置就是left0

再看[0，4]，target=3时，插入位置也是left

或者直接想，最终状态是nums[right]，target，nums[left]，所以把target插在left的位置

二、双指针原地操作数组

1、移除等于val的元素

法一：双指针法

i遍历整个数组，res记录保留下来的数组，都在原地操作

class Solution {
public:int removeElement(vector<int>& nums, int val) {int res=0;for(int i=0;i<nums.size();i++){if(nums[i]!=val){ //如果不等于val，则保留该数组元素（记录下来，在原地数组）nums[res++]=nums[i];}}return res;}
};

法二：有出错的先让后面的来找补

class Solution {
public:int removeElement(vector<int>& nums, int val) {//如果前面有等于val的值，则用后面的值来替补int left=0,right=nums.size()-1;while(left<=right){if(nums[left]==val){ //nums[left]等于val,则让nums[right]来替补（有出错的先让后面的来找补）nums[left]=nums[right--];}else{left++; //nums[left]不等于val,则left继续前行}}return left;}
};

2、移除重复项

class Solution {
public:int removeDuplicates(vector<int>& nums) {int res=0;for(int i=0;i<nums.size();i++){if(i==0||nums[i]!=nums[i-1]){ //如果当前元素不等于前一个元素，说明无重复，录入//（注意：讨论没有前一个元素的情况）nums[res++]=nums[i];}}return res;}
};