题目描述(中等难度)

153. Find Minimum in Rotated Sorted Array - 图1

给定一个特殊升序数组,即一个排序好的数组,把前边的若干的个数,一起移动到末尾,找出最小的数字。

解法一

其实之前已经在 33 题 解法一中写过这个解法了,这里直接贴过来。

求最小值,遍历一遍当然可以,不过这里提到了有序数组,所以我们可以采取二分的方法去找,二分的方法就要保证每次比较后,去掉一半的元素。

这里我们去比较中点和端点值的情况,那么是根据中点和起点比较,还是中点和终点比较呢?我们来分析下。

  • midstart 比较

    mid > start : 最小值在左半部分。

    153. Find Minimum in Rotated Sorted Array - 图2

    mid < start: 最小值在左半部分。

    153. Find Minimum in Rotated Sorted Array - 图3

    无论大于还是小于,最小值都在左半部分,所以 midstart 比较是不可取的。

  • midend 比较

    mid < end:最小值在左半部分。

    153. Find Minimum in Rotated Sorted Array - 图4

    153. Find Minimum in Rotated Sorted Array - 图5

    mid > end:最小值在右半部分。

    153. Find Minimum in Rotated Sorted Array - 图6

    所以我们只需要把 midend 比较,mid < end 丢弃右半部分(更新 end = mid),mid > end 丢弃左半部分(更新 start = mid)。直到 end 等于 start 时候结束就可以了。

但这样会有一个问题的,对于下边的例子,就会遇到死循环了。

153. Find Minimum in Rotated Sorted Array - 图7

问题出在,当数组剩两个的时候,mid = (start + end)/ 2mid 取的就是 start。上图的例子, mid > end, 更新 start = midstart 位置并不会变化。那么下一次 mid 的值也不会变,就死循环了。所以,我们要更新 start = mid + 1,同时也使得 start 指向了最小值。

综上,找最小值的代码就出来了。

  1. public int findMin(int[] nums) {
  2. int start = 0;
  3. int end = nums.length - 1;
  4. while (start < end) {
  5. int mid = (start + end) >>> 1;
  6. if (nums[mid] > nums[end]) {
  7. start = mid + 1;
  8. } else {
  9. end = mid;
  10. }
  11. }
  12. return nums[start];
  13. }

解法二

解法一中我们把 midend 进行比较,那么我们能不能把 midstart 比较解决问题呢?

看一下之前的分析。

midstart 比较

mid > start : 最小值在左半部分或者右半部分。

153. Find Minimum in Rotated Sorted Array - 图8

153. Find Minimum in Rotated Sorted Array - 图9

mid < start: 最小值在左半部分。

153. Find Minimum in Rotated Sorted Array - 图10

上边的问题就出在了 mid > start 中出现了两种情况,如果数组是有序的最小值出现在了左半部分,和mid < start 出现了同样的情况。所以我们其实只需要在更新 startend 之前,判断数组是否已经有序,把这种情况单独考虑。有序的话,直接返回第一个元素即可。

  1. public int findMin(int[] nums) {
  2. int start = 0;
  3. int end = nums.length - 1;
  4. while (start < end) {
  5. if (nums[start] < nums[end]) {
  6. return nums[start];
  7. }
  8. int mid = (start + end) >>> 1;
  9. //必须是大于等于,比如 nums=[9,8],mid 和 start 都指向了 9
  10. if (nums[mid] >= nums[start]) {
  11. start = mid + 1;
  12. } else {
  13. end = mid;
  14. }
  15. }
  16. return nums[start];
  17. }

本质上其实和解法一是一样的。

此外还可以思考一个问题,如果给定的数组经过了一次变化,也就是给定的不是有序的,那么我们是不是就不用在过程中判断当前是不是有序数组了?

答案肯定是否定的了,比如 nums = [4,5,6,1,2,3],经过一次更新,start 会指向 1end 会指向 3,此时就变成有序了,所以在过程中我们必须判断数组是否有序。而解法一的好处就是,即使是有序的,也不影响我们的判断。

二分的方法,主要就是要确定丢弃哪一半。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话,可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法,强烈推荐一个我之前学过的课程,可以点击 这里 查看详情