【算法 day01】LeetCode 704二分查找 | 27移除元素 | 977有序数组的平方
704 二分查找
题目链接：二分查找
文档讲解：代码随想录文章讲解
视频讲解：代码随想录视频讲解
1.暴露破解解法：
public int violentCracking(int[] nums, int target) {for (int i = 0; i < nums.length; i++) {if(nums[i]==target){return i;}}return -1;}时间复杂度:o(n) 空间复杂度:o(1)
2.左闭右闭解法：
2.1思路：
- [left,right],所以一开始left=0,right=nums.length-1,而不能是nums.length
- while循环，当left=right时，[left,right]是有效的区间，所以循环条件是left<=right
- 当中间节点值<target，左节点=middle+1 ,当中间节点>target， 右节点=middle-1 ,当中间节点=target，返回下标
2.2代码：
public int search(int[] nums, int target) {int left=0;//右闭[left,right],所以right是一个被包含在内的值int right=nums.length-1;//right==left,[left,right]是有效的,所以用<=while (left <= right) {int middle=(left+right)/2;if(nums[middle]>target){//[left,right],middle是不符合条件的,所以[left,middle-1]right=middle-1;}if(nums[middle]<target){//[left,right],middle是不符合条件的,所以[middle+1,right]left=middle+1;}if(nums[middle]==target){return middle;}}return -1;}时间复杂度:o(longn) 空间复杂度:o(1)
3.左闭右开解法：
3.1思路：
- [left,right),所以一开始left=0,right=nums.length,保证右区间的值是取不到的
- while循环，left==right时，[left,right)区间无效，所以循环条件是left<right
- 当中间节点值<target，左节点=middle+1 ,当中间节点>target， 右节点=middle ,当中间节点=target，返回下标
3.2代码：
public static int searchRightOpen(int[] nums, int target) {int left=0;//右开[left,right),不包含右区间,所以right=nums.length,但是并不会取到该值int right=nums.length;//右开,[left,right),所以left<right,不能包含=,例[1,1),这个区间无效while (left < right) {int middle = (left + right) / 2;if (nums[middle] > target) {//右开,[left,right),middle是不符和条件的，所以右区间是middle,若写成middle-1,那么就会漏判断right = middle;}if (nums[middle] < target) {//左闭,middle是不满足条件的，所以左区间是middle+1left = middle + 1;}if (nums[middle] == target) {return middle;}}return -1;}时间复杂度:o(logn) 空间复杂度:o(1）
总结：二分法使用条件，数组是升序的，且没有重复元素，写代码的时候，要注意根据区间的定义来判断临界值
27 移除元素
题目链接：移除元素
文档讲解：代码随想录文章讲解
视频讲解：代码随想录视频讲解
1. 思路：
移除数组中等于val的值，并返回数组中不等于val的值个数.
- 不新增数组，使用快慢指针，快指针用于是寻找满足新数组元素(for循环中fast变量),慢指针用于存放到新数组元素的下标
- 快指针找到满足条件的值，放入数组[slow++]中，相当与覆盖原数组中元素
- 慢指针slow的大小就是数组中不等于val的个数
- 注： 数组在[slow+1,nums.length-1]区间仍是有值的，值就是原来对应位置的值
2.代码：
public static 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++;}}System.out.println(Arrays.toString(nums));return slow;}时间复杂度:o(n) 空间复杂度:o(1)
977 有序数组的平方
题目链接：有序数组平方
文档讲解：代码随想录文章讲解
视频讲解：代码随想录视频讲解
1.思路：
题意是将数组元素进行平方，升序排序后返回该数组。数组元素是递增的且存在负数，所以可知最大的元素在原数组的左右两边，考虑使用双指针
- 新建一个数组和一个指针A(初始值是新数组元素的长度，用于记录在新数组哪个位置放元素)
- 使用双指针，初始时分别指向数组第一个元素和最后一个元素
- 循环，判断左指针和右指针平方的大小，将较大的放入新数组中(倒序存放后指针A--)，对应的左指针（left++）或右指针(right--)移动，直到左右指针相遇，结束循环
2.代码：
/*** [-7,-3,2,3,11]* 0 4 121* 0 3 49 121* 1 3 9 49 121* 1 2 9 9 49 121* 2 2 4 9 9 49 121* @param nums* @return*/public static int[] sortedSquares(int[] nums) {int left=0;int right=nums.length-1;int[] newNums=new int[nums.length];int i=newNums.length-1;while (left <= right) {if (nums[left] * nums[left] > nums[right] * nums[right]) {newNums[i] = nums[left] * nums[left];left++;i--;}else {newNums[i] = nums[right] * nums[right];right--;i--;}}return newNums;}时间复杂度o(n) 空间复杂度o(n)