第一章 数组 part01

 今日任务 

数组理论基础，704. 二分查找，27. 移除元素  

 详细布置

 数组理论基础  

文章链接：代码随想录

题目建议： 了解一下数组基础，以及数组的内存空间地址，数组也没那么简单。

 704. 二分查找 

题目建议： 大家能把 704 掌握就可以，35.搜索插入位置 和 34. 在排序数组中查找元素的第一个和最后一个位置 ，如果有时间就去看一下，没时间可以先不看，二刷的时候在看。

先把 704写熟练，要熟悉 根据 左闭右开，左闭右闭 两种区间规则 写出来的二分法。

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

文章讲解：代码随想录

视频讲解：手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili

 27. 移除元素

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

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

文章讲解：代码随想录

视频讲解：数组中移除元素并不容易！ | LeetCode：27. 移除元素_哔哩哔哩_bilibili

---

        对于这个题，满足数组有序，使用左闭右开写法实现

c/c++代码示例如下：

int search(int* nums, int numsSize, int target) {int l=0,r=numsSize;while (l<r){int mid=l+(r-l)/2;if (nums[mid]==target){return mid;}else if (nums[mid]>target){r=mid;}else l=mid+1;}return -1;
}

时间复杂度O(logn) 空间复杂度O(1)

---

         显然暴力法就是遍历数组，当nums[i]==val时，从下标i+1开始所有元素前移一位，并将len-1。（补充：i要及时回溯）

代码示例如下：

int removeElement(int* nums, int numsSize, int val) {int len=numsSize;for (int i=0;i<numsSize-1;i++){if (nums[i]==val){for (int j=i+1;j<numsSize;j++){nums[j-1]=nums[j];}len--;i--;}}return len;
}

这个代码中注意i的回溯，若i不回溯，出现连续val就wa了。时间复杂度O(n^2)。

        优化一下可以这样做：（双指针法-左右指针）

初始化左指针i为数组首，右指针j为数组尾。分别用循环来模拟左指针右移，右指针左移：左指针在nums[i]==val时停下，右指针在nums[j]!=val时停下。然后直接用右指针指向元素覆盖左指针指向元素，当左右相错结束循环，左指针一定指向最终数组尾

代码示例如下：

int removeElement(int* nums, int numsSize, int val) {int pl=0,pr=numsSize-1;while (pl<=pr){while (pl<=pr&&nums[pl]!=val){pl++;}while (pl<=pr&&nums[pr]==val){pr--;}if (pl<pr){nums[pl++]=nums[pr--];}}return pl;
}

还有问题：不取等的话，在相遇时结束循环在[]情况时不对

其他录友的方法：

int removeElement(vector<int>& nums, int val) {int k = 0;int n = nums.size();for (int i = 0; i < n; i++) {if (nums[i] != val) {nums[i - k] = nums[i];}else k++;}return n - k;
}

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

还有快慢指针法

// 时间复杂度：O(n)
// 空间复杂度：O(1)
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;}
};