本文详细说明和思路来源于:
视频讲解:
手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili
Leetcode T 704
题目概述1:
思路:
1.因为数组是升序排列,且数组的元素不重复,所以使用二分查找法
2.注意区间问题,判断条件是否能遍历所有下标.
写法1:在闭区间[left,right]中
class Solution { public int search(int[] nums, int target) { int right = nums.length - 1; int left = 0; while(left <= right) { int mid = left + ((right-left) >> 1); if(nums[mid]<target) { left = mid+1; } else if(nums[mid]>target) { right = mid-1; } else { return mid; } } return -1; } }
写法2:在左闭右开区间[left,right)中
class Solution { public int search(int[] nums, int target) { int left = 0, right = nums.length; while (left < right) { int mid = left + ((right - left) >> 1); if (nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; else if (nums[mid] > target) right = mid; } return -1; } }
思考:
第一次想到二分查找还可以按照区间来分
第一种:闭区间
假设在nums[7] = {1,3,5,7,9,11,13}中寻找target 7,取值下标范围是[0,6],因为是闭区间,所以right = nums.length - 1,因此left指针是0,right指针是6,这个时候left == right是有意义的,所以结束条件时left <= right,在进行if else判断之前,mid的值已经更新过了,此时进行+1或-1操作即可.
第二种:左闭右开区间
同样是上述条件,这里我们的right指针就得指向nums.length,也就是7,因为这里是开区间,
left == right 是没有意义的,例如判断到 [3,3) 这个时候就是矛盾的,既指向3又不指向3,所以判断条件就是 left < right,当nums[mid]<targrt的时候,也就是说,所求的值可能在mid的右边,所以left = mid + 1,而nums[mid]>target 的时候,就可能在左边,这个时候注意,是把left赋值为mid而不是mid-1,因为是开区间,mid指向的元素是不会参与下一轮循环的判断的.
注:这里的mid之所以取值是left+((right-left)>>1)而不是直接(right-left)>>1或者是(left+right)//2的原因是,因为(left+right)//2中left和right本身是两个int类型的变量,取值范围是-2147483648 ~ 2147483647,而如果出现两个很接近2147483647的数相加时,很容易出现负数;不使用
(right-left)>>1的原因是,本身这个是能表示left和right指针之间的距离的一半,并不能表示mid的下标,而用left加上距离的一半才更好的表示了mid的下标.
总结:
首先是,这题虽然一眼就能看出来使用二分法解决,但是在看到解法之前,我从来没有想过考虑边界的问题,只能举例去慢慢推导出边界,而且很容易犯一些低级错误.现在有所好转.
题目概述2:
思路:
这题一开始我已经忘记了,只记得在很久以前做过,是看完了卡哥的题解之后才豁然开朗,所以一道题还是得多刷多总结.
1.暴力求解
两层for循环,一层负责遍历数组,一层负责更新数组,由于数组的删除元素不是真正的删除,而是覆盖掉需要删除的元素,所以时间复杂度是O(n^2),因为一旦发现一个目标元素,就让数组目标元素后面的元素向前移动一位,然后让数组的大小-1.
class Solution { public: int removeElement(vector<int>& nums, int val) { int size = nums.size(); for (int i = 0; i < size; i++) { if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位 for (int j = i + 1; j < size; j++) { nums[j - 1] = nums[j]; } i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位 size--; // 此时数组的大小-1 } } return size; } };
2.快慢指针法
定义一个快指针fast负责寻找目标元素val,一个慢指针负责更新数组,当快指针找到目标元素,即nums[fast] == val,此时慢指针就停下来,直到快指针找到不等于目标值的元素,再对nums[slow] = nums[fast]进行赋值操作.
我们举一个例子:nums[6] = {1,2,3,6,3,9}目标值是3
一开始fast 和 slow指针都指向1,发现不相等,fast和slow都向前走,当指向下标2的时候,fast指针继续向前,slow指针停下,找到下标3发现不相等,就再执行一次赋值,然后两个指针一起向前走,依此往复,最后的数组大小其实就是slow指针指向的下标,因为slow指针再结束后还向后移动了一个单位.最后返回slow的下标即可.
这个解法的时间复杂度只有O(n),因为只遍历了一次数组.
class Solution { public int removeElement(int[] nums, int val) { int fast = 0; int slow = 0; for(int i = 0;i<nums.length;i++) { if(nums[fast] == val) { fast++; } else { nums[slow] = nums[fast]; fast++; slow++; } } int t = slow; return t; } }
总结:
需要多训练这种快慢指针解法,多练习,希望这次代码随想录各位都能坚持下去.
