算法打卡day1|数组篇|Leetcode 704.二分查找、27.移除元素

数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合，可以方便的通过下标索引的方式获取到下标下对应的数据。

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

2.数组内存空间的地址是连续的。

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

在C++中二维数组在内存的空间地址是连续，但在java中并不是连续的。

java中的数组排列方式如下，所以Java的二维数组在内存中不是 3*4 的连续地址空间，而是四条连续的地址空间组成！

算法题

Leetcode 704.二分查找

题目链接:二分查找

大佬视频讲解：手把手带你撕出正确的二分法

个人思路

题目要求是用二分法；那具体步骤为：找到数组中间的值，将这个值循环与目标值对比，1.若找到目标值放回下标2.没找到目标值的话，则按照与目标值对比的大小，重新选择范围，再选择这个范围中的中间值继续对比；但这其中比较难解决的是范围的确定。

解法

这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因此以后遇到此种类型都可以考虑使用二分法；

二分法中，对区间的定义很重要。区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

二分法第一种写法:左闭右闭

即[left, right]；左闭右闭要注意以下两点

1. 循环while中的判断条件 “(left <= right) ”要使用 <= ，因为left == right是有意义的。
2. 目标值小于中间值，右区间需要改变时；right 要赋值为 mid - 1，因为当前这个nums[middle]一定不是target。

class Solution {public int search(int[] nums, int target) {int left=0;int right=nums.length-1;//定义target在左闭右闭的区间里，[left, right]if(target <nums[0]||target>nums[right-1]){//避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算return -1;}while(left<=right){int mid=left+((right-left)>>1);//防止溢出;>> 是右移位运算符,相当于除以 2 并向下取整if(nums[mid]==target){return mid;}else if(nums[mid]<target){//target 在右区间，即[mid + 1, right]left=mid+1;}else if(nums[mid]>target){//target 在左区间，即[left, mid- 1]right=mid-1;}}return -1;}
}

时间复杂度:O(log n)；（折半循环）

空间复杂度:O(1);（没有使用多余空间）

二分法第二种写法:左闭右开

即[left, right)；左闭右开要注意以下两点

1. 循环while中的判断条件“(left < right)”，这里使用 < ,因为left == right在区间[left, right)是没有意义的
2. 目标值小于中间值，右区间需要改变时， right 更新为 mid，因为下一个查询区间不会去比较nums[middle]

class Solution {public int search(int[] nums, int target) {int left=0;int right=nums.length;//定义target在左闭右开的区间里，[left, right]if(target <nums[0]||target>nums[right-1]){//避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算return -1;}while(left<right){int mid=left+((right-left)>>1);//防止溢出;>> 是右移位运算符,相当于除以 2 并向下取整if(nums[mid]==target){return mid;}else if(nums[mid]<target){//target 在右区间，即[mid + 1, right)left=mid+1;}else if(nums[mid]>target){//target 在左区间，即[left, mid)right=mid;}}return -1;}
}

时间复杂度:O(log n)；（折半循环）

空间复杂度:O(1);（没有使用多余空间）

Leetcode27.移除元素

题目链接:27.移除元素

大佬视频讲解：数组中移除元素并不容易

个人思路

因为数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖，所以若要暴力解决的话，得两次循环，一次循环找与目标值对应的，二次循环将删除元素其后面的元素向前赋值；

这种解法慢，也可以换成双指针来解决，指针分为快慢指针，快指针找需要删除的元素，慢指针找新数组的下标；

解法

暴力解法

双重循环

class Solution {public int removeElement(int[] nums, int val) {int len= nums.length;for (int i = 0; i < len; i++) {if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位for (int j = i + 1; j < len; j++) {nums[j - 1] = nums[j];}i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位len--; // 此时数组的大小-1}}return len;}
}

时间复杂度:O(n^2)；（两个for循环 n*n）

空间复杂度:O(1);（没有使用多余空间）

快慢双指针

搞清楚双指针的定义非常关键，快指针的作用是寻找新数组的元素 ，新数组就是不含有目标元素的数组；慢指针的作用是指向更新 新数组下标的位置

class Solution {public int removeElement(int[] nums, int val) {int slow=0;//慢指针for(int fast=0;fast<nums.length;fast++){if(nums[fast]!=val){//如果没有找到目标元素则一起向前遍历nums[slow]=nums[fast];slow++;}}return slow;}
}

时间复杂度:O( n)；（一个for循环）

空间复杂度:O(1);（没有使用多余空间）

以上是个人的思考反思与总结，若只想根据系列题刷，参考卡哥的网址代码随想录算法官网