Day1 数组第一章part01

1.数组理论基础

重点：

• 数组是存放在连续内存空间上的相同类型数据的集合。

• 数组下标都是从0开始的。

• 数组内存空间的地址是连续的。正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

例如删除下标为3的元素，需要对下标为3的元素后面的所有元素都要做移动操作，如图所示：

而且大家如果使用C++的话，要注意vector 和 array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。

数组的元素是不能删的，只能覆盖。

• 代码测试

void test_arr() {
    int array[2][3] = {
		{0, 1, 2},
		{3, 4, 5}
    };
    cout << &array[0][0] << " " << &array[0][1] << " " << &array[0][2] << endl;
    cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;
}

int main() {
    test_arr();
}

输出：

00000066BD4FF5A8 00000066BD4FF5AC 00000066BD4FF5B0
00000066BD4FF5B4 00000066BD4FF5B8 00000066BD4FF5BC

2. 704.二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

左闭右闭

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;  //定义为左闭右闭
        while(left<=right){
            int middle=left+((right-left)/2);  //这个是为了防止int型加法后溢出，具体原因还需有时间再探索。
            //int middle=left+((right-left)/2);  //这样也不会错
            if(target<nums[middle]){
                right=middle-1;
            }else if(target>nums[middle]){
                left=middle+1;   //此处马虎，写成了left=middle—1
            }else{
                return middle;
            }
        }
        return -1;
    }
};

时间复杂度：O(logn) 后续要手推，不要看别人的

空间复杂度：O(1)

左闭右开

其实左闭右闭完全靠理解做对，左闭右开就ok的。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size();  //定义为左闭右开
        while(left<right){  //left和right就不能等于了
            // int middle=(left+right)/2;
            int middle=left+((right-left)/2);
            if(target<nums[middle]){
                right=middle;
            }else if(target>nums[middle]){
                left=middle+1;
            }else{
                return middle;
            }
        }
        return -1;
    }
};

3. 27.移除元素

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

暴力解法

最外层for循环用来遍历数组，内层for循环用来将当前要删除元素后面的元素前移。

这里还要注意一点就是nums传到函数里是以引用的方式，对于调用者来说是可见的，也就是nums在removeElement函数里没有被拷贝过去使用，而是直接将其修改。（这里对传参方式还有点记忆，但是需要复习）

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--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;

    }

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

空间复杂度：O(1)

双指针（快慢指针）

通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

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

//双指针解法   不改变元素的相对位置
int removeElement(vector<int>& nums, int val) {
	int slowIndex = 0;
	for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
		if (nums[fastIndex] != val) {
			nums[slowIndex++] = nums[fastIndex];
		}
	}
	return slowIndex;
}

//双指针解法 改变元素的相对位置，让元素移动最少
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;           //将nums[leftIndex]写成了leftIndex，right那也是
		}
		//右边找到与val值不相等的
		while (leftIndex <= rightIndex && nums[rightIndex] == val) {
			--rightIndex;
		}
		if (leftIndex <= rightIndex) {
			nums[leftIndex++] = nums[rightIndex--];  //用右边与val值不相等的替换掉左边与val值相等的
		}
	}
	return leftIndex;
}

注意这段代码马虎的点