成都专业做网站推广电话,重庆市建设执业注册中心网站,中国十大网站开发公司,网站建设计入什么费用1. 二分查找#xff08;704#xff09;
题目描述#xff1a; 算法原理#xff1a; 暴力解法就是遍历数组来找到相应的元素#xff0c;使用二分查找的解法就是每次在数组中选定一个元素来将数组划分为两部分#xff0c;然后因为数组有序#xff0c;所以通过大小关系舍弃…1. 二分查找704
题目描述 算法原理 暴力解法就是遍历数组来找到相应的元素使用二分查找的解法就是每次在数组中选定一个元素来将数组划分为两部分然后因为数组有序所以通过大小关系舍弃一部分数组最终不断重复这个过程完成查找时间复杂度可以达到logN。 代码如下
class Solution {public int search(int[] nums, int target) {int left 0;int right nums.length-1;while (right left) {int mid left (right - left) / 2;if (nums[mid] target) {right mid - 1;} else if (nums[mid] target) {left mid 1;} else {return mid;}}return -1;}
}题目链接
2. 在排序数组中查找元素的第一个和最后一个位置34
题目描述 朴素二分查找 这题我们可以先使用朴素二分查找的方法取找到等于target的元素下标此时再分别使用两个循环去比较左右两边元素是否与target相等如果相等则分别向左和向右移动最终返回对应的下标即可这个过程很好理解。 代码如下
class Solution {public int[] searchRange(int[] nums, int target) {int left 0, right nums.length - 1;int index1 -1, index2 -1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {left mid 1;} else if (nums[mid] target) {right mid - 1;} else {index1 mid;index2 mid;while (index1 - 1 0 nums[index1] nums[index1 - 1]) {index1--;}while (index2 1 nums.length nums[index2] nums[index2 1]) {index2;}break;}}return new int[] { index1, index2 };}
}优化朴素二分查找 首先我们去寻找target的左边界为了便于理解我们给出图1数组的元素可以分为两个部分前半部分是小于target的元素后一部分是大于等于target的部分。 图1 如图2当我们的nums[mid]也就是x落入前半部分的时候为了去接近target需要使得leftmid1当我们的x落入后半部分的时候此时我们不能够使rightmid-1因为如果说此时x是等于target的并且是左边的最后一个target那么将right-1后面就直接再也找不到正确的target了。综上如果x落入图1的第二段区间那么就使得rightmid。很好理解的一点就是通过这样的操作left在不断的向右移动right在不断的向左移动但是它的下标也不会超出图1第二段区间的左边这样我们就能够找到连续target的左边界。 图2 然后我们来处理两个细节问题第一个问题就是这样使用二分查找它的循环条件是使用leftright还是leftright。我们朴素二分查找是使用后者的但是在这里要使用前者。为什么呢这里先分三种情况 1target在right和left区间之内 在这种情况下最终right会等于left此时跳出循环即可直接得到的下标就是正确答案根本不需要去额外在循环当中去分三种情况 。 2left和right区间内都是小于target的 此时left不断的加一最终和right相等跳出循环即可然后判断nums[right]是否等于target。 3left和right区间内都是大于target 此时right不断向右最终和left相等跳出循环。 以上是选择leftright的原因之一另一个原因就是使用leftright会造成死循环当我们使用图2中的方法来处理最终得到结果时此时left等于right如果使用leftright下一次不会跳出而是会进入死循环这一点还是很好理解的。 综上三种情况我们使用leftright这样的循环条件是因为当跳出循环时我们可以进行判断nums[right]是否等于target从而直接得到结果另外可以防止死循环。 第二个细节问题就是中点的选择一般是有两种方式来计算中点如图3。 图3 图3中两种计算中点的方式在朴素二分查找中都是可以适用的但是这里也就是按照图2的计算方式来说两种方式是有差别的如果我们使用第二种计算方式如果我们将left和right的区间缩小到两个元素也就是left1等于right这种情况此时mid计算为rightnums[mid]等于targetrightmid后面的循环mid经过计算又等于原来的值由此进入死循环为了避免这种情况我们就需要使用第一种计算中点的方式。 以上就是求连续的target左边界的分析对于右边界的分析也是类似的唯一需要注意的就是此时计算中点的方式要选择第二种否则会造成死循环。 优化后代码如下
class Solution {public int[] searchRange(int[] nums, int target) {int left1 0, right1 nums.length - 1;if (right1 -1) {return new int[] { -1, -1 };}int[] ret new int[2];while (left1 right1) {int mid1 left1 (right1 - left1) / 2;if (nums[mid1] target) {left1 mid1 1;} else {right1 mid1;}}if (nums[right1] target) {ret[0] right1;} else {ret[0] -1;}int left2 0, right2 nums.length - 1;while (left2 right2) {int mid2 left2 (right2 - left2 1) / 2;if (nums[mid2] target) {right2 mid2 - 1;} else {left2 mid2;}}if (nums[left2] target) {ret[1] left2;} else {ret[1] -1;}return ret;}
}解题模板 下面出现减一上面就需要加一。 题目链接
3. 搜索插入位置35
题目描述
算法原理 根据题目知道这里的数组是一个升序并且无重复元素的数组并且如果数组内包含target就求出target的下标如果数组中不包含target就求出第一个大于target的数的下标这就是题目的要求。那么我们就可以将数组分为两部分第一部分是小于target的部分第二个部分是大于等于target的部分那么我们直接求出第二部分的左边界即可。前面的题目我们也给出了模板以及解题的思路具体看代码。 代码如下
class Solution {public int searchInsert(int[] nums, int target) {int left 0, right nums.length - 1;if (nums[right] target) {return right 1;}while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {left mid 1;} else {right mid;}}return right;}
}题目链接
4. x 的平方根 69
题目描述
算法原理 根据题目我们知道可以将1到x就当成数组中的数然后我们需要去找到一个数n去满足n*n等于x这个n就可以使用二分查找来进行寻找将1到x分为两部分一部分是数的平方小于等于x另一部分是数的平方大于x显然我们只需要找到第一部分的右边界即可。不过这题提交的时候要注意数据溢出的问题要确定好数的类型。 代码如下
class Solution {public int mySqrt(int x) {if (x 0) {return 0;}int right x, left 1;while (left right) {long mid left (right - left 1) / 2;if (mid * mid x) {left (int) mid;} else {right (int) mid - 1;}}return left;}
}题目链接
