剑指offer 面试题11. 旋转数组的最小数字（易）& LeetCode 154. 寻找旋转排序数组中的最小值 II（难）

如何在旋转之后的数组[1, 2, 3, 4, 5] -> [3, 4, 5, 1, 2] 中寻找最小的数子？如果有重复数字，时间复杂度会发生什么变化？

Tag

二分查找和搜索

问题与解答

问：如何在旋转之后的数组[1, 2, 3, 4, 5] -> [3, 4, 5, 1, 2] 中寻找最小的数子？ 答：二分查找解决

问：如果有重复数字，时间复杂度会发生什么变化？ 答：无重复数字，所有情况都可以用二分查找解决，时间复杂度为 \(O(logN)\)。有重复数字时，只能循环遍历解决，这种特殊情况下时间复杂度为 \(O(n)\)。

本题考点

考查应聘者对二分查找的理解。本题变换了二分查找的条件，输入的数组不是排序的，而是排序数组的一个旋转。这要求我们对二分查找的过程有深刻的理解。 考查应聘者的沟通能力和学习能力。本题面试官提出了一个新的概念：数组的旋转。我们要在很短的时间内学习、理解这个新概念。在面试过程中，如果面试官提出新的概念，那么我们可以主动和面试官沟通，多问几个问题，把概念弄清楚。 考查应聘者思维的全面性。排序数组本身是数组旋转的一个特例。另外，我们要考虑到数组中有相同数字的特例。如果不能很好地处理这些特例，就很难写出让面试官满意的完美代码。

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [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
测试用例设计： - 功能测试（输入的数组是升序排序数组的一个旋转，数组中有重复数字或者没有重复数字）。 - 边界值测试（输入的数组是一个升序排序的数组，只包含一个数字的数组）。 - 特殊输入测试（输入空数组）。

直觉

我们注意到旋转之后的数组实际上可以划分为两个排序的子数组，而且前面子数组的元素都大于或者等于后面子数组的元素。我们还注意到最小的元素刚好是这两个子数组的分界线。在排序的数组中我们可以用二分查找法实现 \(O(logN)\) 的查找。本题给出的数组在一定程度上是排序的，因此我们可以试着用二分查找法的思路来寻找这个最小的元素。

首先，我们用两个指针分别指向数组的开始 index1 和结尾 index2。接着，我们计算出中间位置 indexMid = (index1 + index2) // 2，比较中间位置的数值 numbers[indexMid] 和开始位置 numbers[index1] 的大小关系，因为旋转之后的数组实际上可以划分为两个排序的子数组 A 和 B， 且存在关系，A 的元素都大于或者等于 B 的元素。

所以，当 numbers[indexMid] >= numbers[index1] 时，说明 indexMid 在 A 中，所以 index1 后移到 indexMid 的位置，即 index1 = indexMid。

否则，当 numbers[indexMid] <= numbers[index2] 时，说明 indexMid 在 B 中，所以 index2 前移到 indexMid 的位置，即 index2 = indexMid。

最终第一个指针 index1 将指向前面子数组 A 的最后一个元素，而第二个指针 index2 会指向后面子数组 B 的第一个元素。也就是它们最终会指向两个相邻的元素，而第二个指针指向的刚好是最小的元素，这就是循环终止条件 index2 - index1 == 1 。

两种特殊情况： 1、输入为未旋转数组。设置 indexMid = index1，并设置二分查找循环条件为 while numbers[index1] >= numbers[index2]:，当未旋转时，不会执行二分查找逻辑，直接 return numbers[indexMid] ，也就是 return numbers[index1]，然而，未旋转时，位于数组最前面的 numbers[index1] 就是最小数字了。 2、输入存在重复数字。如进入重复数字区间，就直接去执行时间复杂度为 \(O(n)\) 的顺序查找，不再二分查找了。

1
2
if numbers[index1] == numbers[index2] == numbers[indexMid]:
    return self.minInOrder(numbers, index1, index2)

代码

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:
    def findMin(self, numbers: List[int]) -> int:
        """寻找旋转数组（可能重复）中的最小数字
        """
        if not len(numbers):  return -1
        if len(numbers) == 1:  return numbers[0]  # 这里需要加一个numbers长度为1时的特判。
        index1 = 0
        index2 = len(numbers) - 1
        indexMid = index1
        while numbers[index1] >= numbers[index2]:
            if index2 - index1 == 1:  # 满足终止条件
                indexMid = index2
                break
            indexMid = (index1 + index2) // 2
            if numbers[index1] == numbers[index2] == numbers[indexMid]:  # 有重复就执行该顺序查找操作
                return self.minInOrder(numbers, index1, index2)
            if numbers[indexMid] >= numbers[index1]:
                index1 = indexMid
            elif numbers[indexMid] <= numbers[index2]:
                index2 = indexMid
        return numbers[indexMid]

    def minInOrder(self, numbers, index1, index2):
        """顺序查找，适用于numbers中存在重复元素时
        """
        res = numbers[index1]
        for i in range(index1+1, index2+1):
            if res > numbers[i]:
                res = numbers[i]
        return res

举一反三

本题和 154. 寻找旋转排序数组中的最小值 II 一模一样，代码不变。 153. 寻找旋转排序数组中的最小值 是本题不存在重复数字的特殊情况，相较于154题，去掉了对重复数字特殊处理的部分。代码如下：

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:
    def findMin(self, numbers: List[int]) -> int:
        """寻找旋转数组（可能重复）中的最小数字
        """
        if not len(numbers):  return -1
        if len(numbers) == 1:  return numbers[0]  # 这里需要加一个numbers长度为1时的特判。
        index1 = 0
        index2 = len(numbers) - 1
        indexMid = index1
        while numbers[index1] >= numbers[index2]:
            if index2 - index1 == 1:  # 满足终止条件
                indexMid = index2
                break
            indexMid = (index1 + index2) // 2
            # if numbers[index1] == numbers[index2] == numbers[indexMid]:  # 没有重复就不可能出现这种情况
            #     return self.minInOrder(numbers, index1, index2)
            if numbers[indexMid] >= numbers[index1]:
                index1 = indexMid
            elif numbers[indexMid] <= numbers[index2]:
                index2 = indexMid
        return numbers[indexMid]

    # def minInOrder(self, numbers, index1, index2):
    #     """顺序查找，适用于numbers中存在重复元素时
    #     """
    #     res = numbers[index1]
    #     for i in range(index1+1, index2+1):
    #         if res > numbers[i]:
    #             res = numbers[i]
    #     return res