各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 74 天。今天力扣上的每日一题是「153. 寻找旋转排序数组中的最小值」。

解题思路

今天的题目跟昨天的很类似。遇到「旋转排序数组」的题目，一般可以使用「二分查找」。能用到「减治」思想的，一般都可以用二分查找。「减治」思想，就是排除法，能排除掉部分元素不符合要求的元素，这样会让搜索空间持续降低。

对于题目给出的「旋转排序数组」，假设最小值出现的位置是 pivot， 那么 [0:pivot - 1] 内的元素一定都比 [pivot:N - 1] 大，而且 [0:pivot - 1] 和 [pivot:N - 1] 两个区间内是单调递增的，。所以我们根据二分的中点 mid 的元素大小 和 nums[left] 比较，就能知道当前的 mid 是处于 [0:pivot - 1] 中，还是 [pivot:N - 1] 中。

我们定义 left 和 right 分别指向包含 最小值 pivot 的区间左右边界，闭区间。

  • 当在刚开始搜索时 nums[left] < nums[right] ，那么说明数组是有序的，直接返回 left 位置。
    - 否则，输入是一个旋转有序数组，则 pivot 在 left 和 right 之中，根据定义，在 left 和 right 移动的过程中也一定有 nums[left] > nums[right]。

用例子 [3, 4, 5, 1, 2] 来说明这个过程。

首先 left 和 right 分别指向数组的第 0 个位置和第 4 个位置，mid 指向第 2 个位置。此时发现 nums[mid] >= nums[left]，这说明 mid 处于 [0:pivot - 1] 中，所以最小值元素一定在 mid 的右边，故让 left 指向 mid 位置。

然后 left 和 right 分别指向数组的第 2 个位置和第 4 个位置，mid 指向第 3 个位置。此时发现 nums[mid] < nums[left]，这说明 mid 处于 [pivot: N - 1] 中，所以 最小元素一定在 mid 的左边，故让 right 指向 mid 位置。

然后 left 和 right 分别指向数组的第 2 个位置和第 3 个位置，此时发现 left 和 right 相邻，由于 pivot 一定在 [left, right] 之间，如果 left 和 right 相邻，说明最小的元素一定是 right 了。

代码如下：

  1. class Solution(object):
  2.     def findMin(self, nums):
  3.         if len(nums) == 1: return nums[0]
  4.         left, right = 0, len(nums) - 1
  5.         mid = left
  6.         while nums[left] >= nums[right]:
  7.             if left + 1 == right:
  8.                 mid = right
  9.                 break
  10.             mid = (left + right) / 2
  11.             if nums[mid] >= nums[left]:
  12.                 left = mid + 1
  13.             elif nums[mid] <= nums[right]:
  14.                 right = mid
  15.         return nums[mid]
  • 时间复杂度：$O(log(N))$
  • 空间复杂度：$O(1)$

刷题心得

这两天的题目都可以直接线性遍历通过评测，但是在面试的过程中，面试官肯定不满意于$O(N)$的写法，所以还是要老老实实学习二分查找。

参考资料：
《剑指Offer》

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！