目录

• • • 数组理论基础、二分查找、移除元素
    • • 1.数组理论基础
      • 2.Leetcode704.二分查找
      • • 方法一 左闭右闭：
        • 方法二 左闭右开：
        • 方法三 左开右开：
        • 方法四 左开右闭：
      • 3.Leetcode27. 移除元素
      • • 方法一 暴力解法
        • 方法二 双指针法

数组理论基础、二分查找、移除元素

1.数组理论基础

题目建议：了解数组基础，以及数组的内存空间地址

• 数组是存放在连续内存空间上的相同类型数据的集合
• 数组的元素是不能删的，只能覆盖：平时删除操作也是依次用后一位覆盖，因为申请且初始化后，存储空间就固定了

验证数组在内存的空间地址是否连续:

#include <iostream>         // 包含头文件。
using namespace std;        // 指定缺省的命名空间。

void test_arr() {			//创建一个3*3的二维数组，并打印内存地址
	int array[3][3] = {
		{1,2,3},
		{4,5,6},
		{7,8,9}
	};
	cout << &array[0][0] << " " << &array[0][1] << " " << &array[0][2] << endl;
	cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;
	cout << &array[2][0] << " " << &array[2][1] << " " << &array[2][2] << endl;
};

int main()
{
	test_arr();
}

输出的测试地址：

000000B846EFF668 000000B846EFF66C 000000B846EFF670
000000B846EFF674 000000B846EFF678 000000B846EFF67C
000000B846EFF680 000000B846EFF684 000000B846EFF688

2.Leetcode704.二分查找

题目建议： 掌握704.二分查找，先把 704写熟练，要熟悉 根据 左闭右开，左闭右闭 两种区间规则 写出来的二分法。拓展看一下：35.搜索插入位置 和 34. 在排序数组中查找元素的第一个和最后一个位置

思路：

• 二分法的前提条件：1.数组为有序数组 2.数组中无重复元素
• 循环不变量规则：区间的定义就是不变量，在while寻找中每一次边界的处理都要坚持根据区间的定义来操作
• 写二分法，区间的定义一般为两种：左闭右闭即[left, right]，或者左闭右开即[left, right)。

方法一 左闭右闭：

//方法一 力扣一次AC
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left =0;
        int right=nums.size()-1;  // 定义target在左闭右闭的区间里，[left, right]，根据区间定义让所有元素在该区间内
        while(left <= right){     // 当left==right，区间[left, right]依然有效，所以用 <=   例：[2,2]
            int mid=left + ((right - left) / 2); // 防止溢出 等同于(left + right)/2
            if(nums[mid]>target){
                right=mid-1;      // target 在左区间，所以[left, middle - 1]
            }
            else if(nums[mid]<target){
                left=mid+1;       // target 在右区间，所以[middle + 1, right]
            }		
            else{			     // nums[middle] == target
                return mid;		 // 数组中找到目标值，直接返回下标
            }
        }
        return -1;				//未找到目标值
    }
};

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

方法二 左闭右开：

//方法二 力扣一次AC
class Solution {
public:
    int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size();      // 定义target在左闭右开的区间里，即：[left, right) 根据区间定义让所有元素在该区间内
    while (left < right){		  // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <  例：[2,2)
       int mid = left + (right-left)/2;// 防止溢出 等同于(left + right)/2
        if (nums[mid] > target){
            right = mid;		// target 在左区间，在[left, middle)中
        }
        else if (nums[mid] < target){
            left = mid + 1;		// target 在右区间，在[middle + 1, right)中
        }
        else{					 // nums[middle] == target
            return mid;			// 数组中找到目标值，直接返回下标
        }
     
    }
    return -1 ;					//未找到目标值
    }					
};

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

方法三 左开右开：

// 方法三 左开右开 未考虑区间定义，超出内存限制一次
class Solution {
public:
    int search(vector<int>& nums, int target) {
    int left = -1;
    int right = nums.size();
    while (left < right-1){    //这里一定考虑区间是否有意义 例如：(2,3)也是没有意义的
       int mid = left + (right-left)/2;
        if (nums[mid] > target){
            right = mid;
        }
        else if (nums[mid] < target){
            left = mid ;
        }
        else{
            return mid;
        }
     
    }
    return -1 ;
    }
};

方法四 左开右闭：

class Solution {
public:
    int search(vector<int>& nums, int target) {
    int left = -1;
    int right = nums.size()-1;
    while (left < right){
       int mid = ( (left + right + 1) / 2) ;
        if (nums[mid] > target){
            right = mid -1;
        }
        else if (nums[mid] < target){
            left = mid ;
        }
        else{
            return mid ;
        }
     
    }
    return -1 ;
    }
};

3.Leetcode27. 移除元素

题目建议： 27.移除元素，暴力的解法，可以锻炼一下我们的代码实现能力，建议先把暴力写法写一遍。 双指针法 是本题的精髓，今日需要掌握，至于拓展题目可以先不看。

思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

方法一 暴力解法

这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。

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++){	//从i后面一位开始往前移一位
                     nums[j-1]=nums[j];
                 }
                 i--;		// 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                 size--;	// 此时数组的大小-1
            }
           
        }
        return size;
    }
};

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

方法二 双指针法

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作

双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        int slow = 0;
        for(int i =0;i < size;i++){
            if(nums[i]!=val){
                nums[slow]=nums[i];
                slow++;
            }
        }
        return slow;
    }
};

/**
* 相向双指针方法，基于元素顺序可以改变的题目描述改变了元素相对位置，确保了移动最少元素
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int leftIndex = 0;
        int rightIndex = nums.size() - 1;
        while (leftIndex <= rightIndex) {
            // 找左边等于val的元素
            while (leftIndex <= rightIndex && nums[leftIndex] != val){
                ++leftIndex;
            }
            // 找右边不等于val的元素
            while (leftIndex <= rightIndex && nums[rightIndex] == val) {
                -- rightIndex;
            }
            // 将右边不等于val的元素覆盖左边等于val的元素
            if (leftIndex < rightIndex) {
                nums[leftIndex++] = nums[rightIndex--];
            }
        }
        return leftIndex;   // leftIndex一定指向了最终数组末尾的下一个元素
    }
};