剑指offer刷题6——查找算法(中等)

剑指 Offer 11. 旋转数组的最小数字

难度 简单

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2][1,2,3,4,5] 的一个旋转,该数组的最小值为1。

示例 1:

1
2
输入:[3,4,5,1,2]
输出:1

示例 2:

1
2
输入:[2,2,2,0,1]
输出:0

注意:本题与主站 154 题相同:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

思路

解题思路: 为精简篇幅,本文将数组 numbers 缩写为 nums

如下图所示,寻找旋转数组的最小元素即为寻找 右排序数组 的首个元素 nums[x] ,称 x 为 旋转点 。

Picture1.png

排序数组的查找问题首先考虑使用 二分法 解决,其可将 遍历法 的 线性级别 时间复杂度降低至 对数级别 。

算法流程

  1. 初始化: 声明 i, j 双指针分别指向 nums 数组左右两端;
  2. 循环二分: 设 m = (i + j) / 2为每次二分的中点( "/" 代表向下取整除法,因此恒有 \(i \leq m < j\) ),可分为以下三种情况:
    1. 当 nums[m] > nums[j] 时: m 一定在 左排序数组 中,即旋转点 x 一定在 [m + 1, j] 闭区间内,因此执行 i = m + 1;
    2. 当 nums[m] < nums[j]时: m 一定在 右排序数组 中,即旋转点 x 一定在[i, m] 闭区间内,因此执行 j = m;
    3. 当 nums[m] = nums[j]时: 无法判断 m 在哪个排序数组中,即无法判断旋转点 x 在 [i, m] 还是 [m + 1, j] 区间中。解决方案: 执行 j -- 缩小判断范围,分析见下文。
  3. 返回值: 当 i = j时跳出二分循环,并返回 旋转点的值 nums[i] 即可。

正确性证明: 当 nums[m] = nums[j]] 时,无法判定 m 在左(右)排序数组,自然也无法通过二分法安全地缩小区间,因为其会导致旋转点 x 不在区间 [i, j] 内。举例如下:

设以下两个旋转点值为 00 的示例数组,则当 i = 0,j=4 时 m = 2 ,两示例结果不同。 示例一 [1, 0, 1, 1, 1]:旋转点 x = 1,因此 m = 2在 右排序数组 中。 示例二 [1, 1, 1, 0, 1]:旋转点 x = 3 ,因此 m= 2 在 左排序数组 中。

而证明 j = j - 1 正确(缩小区间安全性),需分为两种情况:

  1. 当 x < j 时: 易得执行 j = j - 1 后,旋转点 xx 仍在区间 [i, j]内。

  2. 当 x = j 时: 执行 j = j - 1后越过(丢失)了旋转点 x ,但最终返回的元素值 nums[i] 仍等于旋转点值 nums[x] 。

    1. 由于 x = j ,因此 \(nums[x] = nums[j] = nums[m] \leq number[i]\);
    2. 又由于 \(i \leq m <j\)恒成立,因此有 m < x ,即此时 m 一定在左排序数组中,因此 \(nums[m] \geq nums[i]\) ; 综合 1. , 2. ,可推出 nums[i] = nums[m]nums[i]=nums[m] ,且区间 [i, m][i,m] 内所有元素值相等,即有: \[ nums[i] = nums[i+1] = \cdots = nums[m] = nums[x] \]
  • 此时,执行 j = j - 1 后虽然丢失了旋转点 xx ,但之后区间 [i, j] 只包含左排序数组,二分下去返回的一定是本轮的 nums[i],而其与 nums[x] 相等。
  • 综上所述,此方法可以保证返回值 nums[i] 等于旋转点值 nums[x] ,但在少数特例下 \(i \ne x\) ;而本题目只要求返回 “旋转点的值” ,因此本方法正确。

补充思考: 为什么本题二分法不用 nums[m] 和 nums[i] 作比较?

二分目的是判断 m 在哪个排序数组中,从而缩小区间。而在 nums[m] > nums[i]情况下,无法判断 mm 在哪个排序数组中。本质上是由于 j 初始值肯定在右排序数组中; i 初始值无法确定在哪个排序数组中。举例如下:

对于以下两示例,当 i = 0, j = 4, m = 2 时,有 nums[m] > nums[i] ,而结果不同。 [1, 2, 3, 4 ,5]旋转点 x = 0 : m 在右排序数组(此示例只有右排序数组); [3, 4, 5, 1 ,2]旋转点 x = 3 : m 在左排序数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int minArray(vector<int>& numbers) {
int Left,Right,mid;
Left = 0; Right = numbers.size()-1;
while(Left < Right)
{
mid = (Left+Right)/2;
if(numbers[mid] > numbers[Right]) Left = mid+1;
else if(numbers[mid] < numbers[Right]) Right = mid;
else if(numbers[mid] == numbers[Right]) Right--;
}
return numbers[Left];
}
};