20230419 | 704.二分查找、27.移除元素

1、数组基础理论

int a[m][n];
数组长度表示：a[0].length
数组宽度表示：a.length

2、704.二分查找

特征：数组是升序的找某个数，那就使用二分法。时间复杂度O(log n)，空间复杂度O(1)
我使用左闭右闭区间
计算中点： int mid = l+((r-l)>>1); int mid = l+(l-r)/2;
注意：int mid = (l+r)/2; (量大容易溢出)

class Solution {public int search(int[] nums, int target) {//升序=》二分查找if(nums.length ==0) return -1;int l=0,r=nums.length-1;while(l<=r){int mid = l+((r-l)>>1);if(target==nums[mid]){return mid;}else if(target>nums[mid]){l = mid+1;}else{r =mid-1;}}return -1;}
}

注意点1：
第一次计算中点：int mid = l+(r-l)>>1；没注意运算符号的优先级。报超出时间复杂度.
应该写为：int mid = l+((r-l)>>1);

注意点2：
这道题写过很多次了，每次判断的时候我都写成：if(target==mid) ，结果运行就不对，我是一个马大哈。
应该写为：if(target==nums[mid]) ，比较的是数组里面的值。

3、27.移除元素

暴力法，找到目标值，然后后面的数全部往前移动一位，数组大小减一
时间复杂度：O(n^2) ，空间复杂度：O(1)

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

双指针法，用一个for代替两个for，时间复杂度为O(n)
定义快慢指针
快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
慢指针：指向更新 新数组下标的位置

   public int removeElement(int[] nums, int val) {//双指针法，定义快慢指针int slowIndex =0;for(int fastIndex = 0;fastIndex<nums.length;fastIndex++){if(nums[fastIndex]!=val){ //值不等时，慢指针+1nums[slowIndex] = nums[fastIndex];slowIndex++;}//值相等时，慢指针不动，快指针多走，等遇到不等时，慢指针指向的值被快指针指向的值覆盖}return slowIndex;}