电子网站模板,html网页框架,网站安全建设思考,长春网长春网站建设站建设文章目录 33.搜索旋转排序数组81.搜索旋转排序数组||153.寻找旋转排序数组中的最小值154.寻找旋转排序数组中的最小值||参考链接 33.搜索旋转排序数组
https://leetcode.cn/problems/search-in-rotated-sorted-array/description/ 下面这张图片是LC154题官方题解提供的一个图… 文章目录 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 1target nums[mid] 时r mid - 1两者相等的情况上面已经判断过了target 位于右边界时mid 位于左边界l mid 1。target 位于右边界时mid 位于右边界target nums[mid] 时l mid 1target 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 1nums[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/
