0%

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

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

题目描述:

给出一个长度为 $n$ 的数组,预先按照升序排列,在下标 $k$ ,经过旋转之后得到新的数组 $[nums[k], …, nums[n-1], nums[0],…, nums[k-1]]$ 。给出一个元素值互不相同的数组 nums,找出其中最小的元素。时间复杂度限制 $O(\log(n))$

数据范围:

$1\le n\le 5000$

题解:

旋转之后的数组满足,观察发现前一段的都大于 $nums[0]$ ,后一段的都小于 $nums[0]$ 。或者前一段的都大于 $nums[n-1]$ ,后一段的都小于 $nums[n-1]$ 。可以根据这个进行二分搜索。如果 $nums[mid]$ 大于 $nums[0]$ ,则 $l = mid + 1$ ;否则 $r = mid - 1$ 。

image-20230509175334757

二分查找如果写成三段的形式 $[l, mid - 1], mid, [mid + 1, r]$ 需要判断 $[l,mid - 1]$ 或者 $[mid + 1, r]$ 能不能划分出来。这个题目里面如果不和 $nums[0]$ 或 $nums[n-1]$ 比较,和 $nums[r]$ 比较,就会遇到这种情况。

一般情况下会写成

1
2
3
4
5
6
7
8
9
10
11
12
13
int l = 0, r = n - 1, ans = -1, mid;
while(l <= r)
{
mid = (l + r) >> 1;
if(nums[mid] > nums[r])
l = mid + 1;
else
{
// nums[mid] <= nums[r]
ans = mid;
r = mid - 1;
}
}

但是当 $nums[mid] <= nums[r]$ 的时候,如果 $nums[mid-1]$ 大于了 $nums[mid]$ 说明 $nums[mid]$ 已经是最优解了,此时 $r = mid-1$ 会跳过最优解,跑到前一段去。二分搜索应该一直留下最优解可能存在的区间,结果留下的不是最优解可能在的区间,所以会出现问题。这时就需要加特殊的判断,如果能分出 $[l,mid-1]$ 下一次就搜索该区间,如果已经找到了最优解直接返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int l = 0, r = n - 1, mid, ans = -1;
while (l <= r)
{
mid = l + r >> 1;
if (nums[mid] > nums[r])
{
l = mid + 1;
}
else if (nums[mid] <= nums[r])
{
ans = mid;
if (mid - 1 >= l && nums[mid - 1] < nums[mid])
// 此处判断最优解是不是在 [l, mid - 1] 区间内部
r = mid - 1;
else
break;
}
}

也可以使用分两段的二分搜索查找最优解。分两段的循环条件是 $l < r$ 保证了最后返回时 $l=r$ ,可以直接得到最优解。并且由于最后一次访问时 $r = l + 1$ ,区间内部是有两个元素的,但是在最后一次循环时会再次分段,只剩下一个元素 $l=r$ ,这个元素就是答案。每次分的时候可能分成 $[l,mid-1],[mid,r]$ ,也可能分成 $[l,mid],[mid+1,r]$ 。当分成 $[l,mid-1],[mid,r]$ 时,需要令 $l = mid$ ,这个地方二分 $mid$ 时需要 $mid = r + l + 1 >> 1$ ,因为如果最后只剩两个元素,求 $mid$ 时向下取整会使得 $mid = l$ ,导致陷入死循环。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:

int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1, ans = -1, mid;
while(l <= r)
{
mid = (l + r) >> 1;
if(nums[mid] < nums[0])
{
ans = mid;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
if(ans == -1) ans = 0;
return nums[ans];
}
};

三段完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution
{
public:
int findMin(vector<int> &nums)
{
int n = nums.size();
if (nums[0] <= nums[n - 1])
return nums[0];
int l = 0, r = n - 1, mid, ans = -1;
while (l <= r)
{
mid = l + r >> 1;
if (nums[mid] > nums[r])
{
l = mid + 1;
}
else if (nums[mid] <= nums[r])
{
ans = mid;
if (mid - 1 >= l && nums[mid - 1] < nums[mid])
{
r = mid - 1;
}
else
break;
}
}
return nums[ans];
}
};

两段完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution
{
public:
int findMin(vector<int> &nums)
{
int n = nums.size();
if (nums[0] <= nums[n - 1])
return nums[0];
int l = 0, r = n - 1, mid;
while (l < r)
{
mid = l + r >> 1;
if (nums[mid] > nums[r])
{
l = mid + 1;
}
else
{
// nums[mid] <= nums[r]
r = mid;
}
}
return nums[l];
}
};