当前位置: 首页> 汽车> 车展 > 北京网站制作策划_html网页制作模板免费_百度搜索seo_网站推广具体内容

北京网站制作策划_html网页制作模板免费_百度搜索seo_网站推广具体内容

时间:2025/7/11 7:48:03来源:https://blog.csdn.net/weixin_45863010/article/details/142663275 浏览次数: 0次
北京网站制作策划_html网页制作模板免费_百度搜索seo_网站推广具体内容

文章目录

  • 33.搜索旋转排序数组
  • 81.搜索旋转排序数组||
  • 153.寻找旋转排序数组中的最小值
  • 154.寻找旋转排序数组中的最小值||
  • 参考链接

33.搜索旋转排序数组

https://leetcode.cn/problems/search-in-rotated-sorted-array/description/
在这里插入图片描述
下面这张图片是LC154题官方题解提供的一个图片:我转载一下:
在这里插入图片描述

上图与本题唯一的区别是:本题题目约束数组中不包含重复元素,所以在某次旋转后,数组一定会被分为「左数组」和「右数组」
其中「左数组」和「右数组」分别单调递增。有一种特殊情况需要注意:
当数组旋转数组长度个单位后,仍然是元素组,此时这个数组也被称为「右数组」,你可能要问为什么要将其称为「右数组」而不是「左数组」,可以使用123三个元素依次旋转就能够观察到,最后一定是「右数组」同时右数组在本题以及后面的题目中,都会作为划分左右数组边界的关键所在。
第一题实现思路:

  • 采用二分法,计算出mid都应的值:num[mid]
  • 如果num[mid] == target,则直接返回。
  • 如果不相等,则需要判断,nums[mid] 和 target的大小关系。此时就涉及到 target 和 nums[mid] 分别位于左边界还是右边界的问题。
  • 我划分的标准是使用 target 和 nums[r] 对比,如果 target > nums[r] 则此时 target 一定位于左边界,如果 target < nums[r] 则此时 target一定位于右边界。在本题中由于不包含重复元素,所以不存在target == nums[r] 的情况,下面一题是这种情况。
  • 当 target 划分好左边边界后,需要使用 nums[mid] 和 nums[r] 的大小关系判断出 mid 位于左右边界的情况,对于左右边界的值分别进行比较。
    • target 位于左边界时,mid 位于右边界:r = mid - 1。
    • target 位于左边界时,mid 位于左边界:target > nums[mid] 时,l = mid + 1;target < nums[mid] 时,r = mid - 1;两者相等的情况上面已经判断过了
    • target 位于右边界时,mid 位于左边界:l = mid + 1。
    • target 位于右边界时,mid 位于右边界:target > nums[mid] 时,l = mid + 1;target < nums[mid] 时,r = mid - 1;

具体代码如下:

class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length - 1;while(l < r){int mid = (l + r) / 2;if(nums[mid] == target){return mid;}if(target > nums[r]){// target位于左边界if(nums[mid] < nums[r]){// mid位于右边界r = mid - 1;}else{// mid位于左边界if(nums[mid] > target){r = mid - 1;}else{l = mid + 1;}}}else{// target位于右边界if(nums[mid] > nums[r]){// mid位于左边界l = mid + 1;}else{// mid位于右边界if(nums[mid] > target){r = mid - 1;}else{l = mid + 1;}}}}System.out.println(l);return nums[l] == target ? l : -1;}
}

81.搜索旋转排序数组||

https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/
在这里插入图片描述
此题就是对上面题目的扩展,上一题目中判断是否位于左边界,直接和nums[r] 相比,大于则位于左边界,随后直接位于右边界,根本不考虑相等的情况,因为第一题元素值不相等,根本不存在 == nums[r] 这中情况。
本题存在相等元素,只需要在上一题的判断的基础上,添加上是否 等于 nums[r] 这种情况即可。
具体见代码及注释:

class Solution {public boolean search(int[] nums, int target) {int l = 0, r = nums.length - 1;while(l < r){int mid = (l + r) / 2;if(nums[mid] == target){return true;}if(target > nums[r]){// 此时target位于左边界数组if(nums[mid] == nums[r]){// mid不确定位于左边界,还是右边界,此时只能缩小右边界的范围r = r - 1;}else if(nums[mid] < nums[r]){// mid位于右边界r = mid - 1;}else{// mid位于左边界if(nums[mid] > target){r = mid - 1;}else{l = mid + 1;}}}else if(target < nums[r]){// 此时target位于右边界数组if(nums[mid] == nums[r]){// mid不确定位于左边界,还是右边界,此时只能缩小右边界的范围r = r - 1;}else if(nums[mid] > nums[r]){// mid位于左边界l = mid + 1;}else{// mid位于右边界if(nums[mid] > target){r = mid - 1;}else{l = mid + 1;}}}else if(target == nums[r]){// target直接和右边界相等,则直接返回return true;}}return nums[l] == target;}
}

153.寻找旋转排序数组中的最小值

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
在这里插入图片描述
这道题目寻找旋转数组的最小值,就是旋转数组的左右边界交界处。
仍然可以利用二分取得mid后和nums[r] 进行比较。

  • nums[mid] > nums[r] : 此时mid位于左边界,肯定不符合要求,直接 l = mid + 1;
  • nums[mid] < nums[r] : 此时mid位于右边界,由于二分查找计算的mid是向下取整的,所以 l <= mid < r ;所以此时直接令 r = mid 即可,不需要额外mid - 1。

代码展示:

class Solution {public int findMin(int[] nums) {int l = 0, r = nums.length - 1;while(l < r){int mid = (l + r) / 2;if(nums[mid] > nums[r]){// 此时mid位于左边界l = mid + 1;}else{// 此时mid位于右边界,由于向下取整,直接 mid = r 主要考虑到r可能此时就是右边界函数的最左边小值r = mid;}}return nums[l];}
}

154.寻找旋转排序数组中的最小值||

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/
在这里插入图片描述
如果对与1题到2题的演化关系比较熟练了,那么此时从3题演化到4题,也可以类比,在3题的基础上添加nums[mid] == num[r] 相等条件的判断即可。
代码演示:

class Solution {public int findMin(int[] nums) {int len = nums.length;int l = 0, r = len - 1;while(l < r){int mid = (l + r) / 2;if(nums[mid] > nums[r]){// 此时m位于左排序数组中l = mid + 1;}else if(nums[mid] < nums[r]){// 此时m位于右排序数组中r = mid;}else{r = r - 1;}}return nums[l];}
}

对于第四题可以参考下述链接加深理解。

参考链接

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/

关键字:北京网站制作策划_html网页制作模板免费_百度搜索seo_网站推广具体内容

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: