立法会记录 1:查找旋转数组的最小值,确定旋转数组中是否存在给定元素 33. 查找旋转排序数组
最编程
2024-10-01 06:57:50
...
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;
}
}
下一篇: II.Pytorch 基本语法