day01 - 数组part01

一、数组基础知识

在C++中，数组在逻辑和物理空间中均是线性连续的，其元素下标从0开始。常见数组的操作：

• 双指针 （快慢指针）
• 覆盖（删除数组元素）
• 交换数组元素（用于排序等）

当然如果用容器的话，像删除和排序可以直接用一些方法来实现

二、二分查找

leetcode 704题

核心思想是不断与中间元素比较，确定是左边的区间还是右边的区间，需要注意的是这里用到的双指针是左闭右闭，即[left,right]，搞清楚这一点就比较容易了。具体代码参考如下：

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

这里还需要理解的是循环结束后left和right的位置，若没有找到元素，left=right+1，从而跳出循环，返回-1。此时left左边的数表示的是比target要小的数（不包括left指向的数本身），而right右边表示比target大的数（不包括right指向的数）。有些题目会利用这一点出题，比如：

leetcode 35 搜索插入位置

class Solution {
public:int searchInsert(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 left = mid+1;}return left;}
};

要找的插入位置其实就是比target大的第一个元素的位置，也就是left。

下面再看一道题是利用两次二分查找确定相同元素的最大最小位置

leetcode 34题 

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int left = 0;int right = nums.size()-1;int first = -1;int last = -1;while(left<=right){int mid = (left+right) / 2;if(nums[mid] == target){first = mid;right = mid - 1; //从左边中继续找相等的元素，直到是最左边为止}else if(nums[mid] > target) right = mid - 1;else left = mid + 1;}left = 0;right = nums.size() - 1;while(left <= right){int mid = (left+mid) / 2;if(nums[mid] == target){last = mid;left = mid+1; //在mid右边继续找有没有相等的元素，直到最右边为止}else if(nums[mid] > target) right = mid - 1;else left = mid + 1;}return vector<int>{first,last};}
};

第一个注释确保了即使找到目标值，也会继续向左搜索，以确保找到第一个出现的索引。
第二个注释确保了即使找到目标值，也会继续向右搜索，以确保找到最后一个出现的索引。

三、移除元素

leetcode 27 移除元素

这道题的本质就是要删除掉指定的元素，一种方法是直接覆盖（暴力），参考代码如下：
 

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

另一种方法是快慢指针，可以直接在原数组上实现覆盖。其中，

快指针：用于遍历旧的数组，来找到符合条件的元素

慢指针：指向新数组下标

参考代码如下：

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

四、有序数组的平方

leetcode 977 有序数组的平方

这道题也是运用了双指针，因为新数组的最大值只可能出现在旧数组的首位，因此我们创建一个新数组，用k指向新数组最后，之后遍历旧数组，看看那边是最大值，就放入新数组中。参考代码如下：

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int k = nums.size()-1; //用于指向新数组的指针vector<int> result(nums.size(),0);for(int i=0,j=nums.size()-1;i<=j;){if(nums[i]*nums[i] < nums[j]*nums[j]){result[k] = nums[j]*nums[j];j--;k--;}else{result[k] = nums[i]*nums[i];i++;k--;}}return result;}
};

总结一下今天刷的题目，通常数组在有时间复杂度要求或滑动窗口的情况下，要考虑用双指针。