优秀的商城网站首页设计,郑州最好的网站建设,公共事业管理专业教材建设研究 教学成果奖申报网站,深圳学校网站建设本文详细说明和思路来源于: 代码随想录 视频讲解: 手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode#xff1a;704. 二分查找_哔哩哔哩_bilibili Leetcode T 704
题目链接 704. 二分查找 - 力扣#xff08;LeetCode#xff09;
题目概述1: 思路:
1.因…本文详细说明和思路来源于: 代码随想录 视频讲解: 手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode704. 二分查找_哔哩哔哩_bilibili Leetcode T 704
题目链接 704. 二分查找 - 力扣LeetCode
题目概述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 mid1;}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或者是(leftright)//2的原因是,因为(leftright)//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(vectorint 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;inums.length;i){if(nums[fast] val){fast;}else{nums[slow] nums[fast];fast;slow;}}int t slow;return t;}
} 总结:
需要多训练这种快慢指针解法,多练习,希望这次代码随想录各位都能坚持下去.
