Huge Lemon的博客

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

2020-01-22

LeetCode上的一道题目：153. 寻找旋转排序数组中的最小值

来源：
https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/solution/xun-zhao-xuan-zhuan-pai-lie-shu-zu-zhong-de-zui-xi/

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。

示例 1:

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

示例 2

输入: [4,5,6,7,0,1,2]
输出: 0

方法：二分查找

思路

一种暴力的解法是搜索整个数组，找到其中的最小元素，这样的时间复杂度是 $O(N)$ 其中 $N$ 是给定数组的大小。

一个非常棒的解决该问题的办法是使用二分搜索。在二分搜索中，我们找到区间的中间点并根据某些条件决定去区间左半部分还是右半部分搜索。

由于给定的数组是有序的，我们就可以使用二分搜索。然而，数组被旋转了，所以简单的使用二分搜索并不可行。

我们希望找到旋转排序数组的最小值，如果数组没有被旋转呢？如何检验这一点呢？

如果数组没有被旋转，是升序排列，就满足 last element > first element。

上图例子中 7 > 2 。说明数组仍然是有序的，没有被旋转。

上面的例子中 3 < 4，因此数组旋转过了。这是因为原先的数组为 [2, 3, 4, 5, 6, 7]，通过旋转较小的元素 [2, 3] 移到了后面，也就是 [4, 5, 6, 7, 2, 3]。因此旋转数组中第一个元素 [4] 变得比最后一个元素大。

这意味着在数组中你会发现一个变化的点，这个点会帮助我们解决这个问题，我们称其为变化点。

在这个改进版本的二分搜索算法中，我们需要找到这个点。下面是关于变化点的特点：

所有变化点左侧元素 > 数组第一个元素
所有变化点右侧元素 < 数组第一个元素

算法

  1. 找到数组的中间元素mid。

  2. 如果中间元素 > 数组第一个元素，我们需要在mid右边搜索变化点。

  3. 如果中间元素 < 数组第一个元素，我们需要在mid做边搜索变化点。

上面的例子中，中间元素6比第一个元素4大，因此在中间点右侧继续搜索。

  1. 当我们找到变化点时停止搜索，当以下条件满足任意一个即可：
    nums[mid] > nums[mid + 1]，因此mid+1是最小值。

    nums[mid - 1] > nums[mid]，因此mid是最小值。

在上面的例子中，标记左右区间端点。中间元素为2，之后的元素是7满足7 > 2也就是nums[mid - 1] > nums[mid]。因此找到变化点也就是最小元素为2。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
  public int findMin(int[] nums) {
    // If the list has just one element then return that element.
    if (nums.length == 1) {
      return nums[0];
    }

    // initializing left and right pointers.
    int left = 0, right = nums.length - 1;

    // if the last element is greater than the first element then there is no rotation.
    // e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.
    // Hence the smallest element is first element. A[0]
    if (nums[right] > nums[0]) {
      return nums[0];
    }
    
    // Binary search way
    while (right >= left) {
      // Find the mid element
      int mid = left + (right - left) / 2;

      // if the mid element is greater than its next element then mid+1 element is the smallest
      // This point would be the point of change. From higher to lower value.
      if (nums[mid] > nums[mid + 1]) {
        return nums[mid + 1];
      }

      // if the mid element is lesser than its previous element then mid element is the smallest
      if (nums[mid - 1] > nums[mid]) {
        return nums[mid];
      }

      // if the mid elements value is greater than the 0th element this means
      // the least value is still somewhere to the right as we are still dealing with elements
      // greater than nums[0]
      if (nums[mid] > nums[0]) {
        left = mid + 1;
      } else {
        // if nums[0] is greater than the mid value then this means the smallest value is somewhere to
        // the left
        right = mid - 1;
      }
    }
    return -1;
  }
}
时间复杂度分析
  • 时间复杂度：和二分搜索一样$O(logN)$
  • 空间复杂度：$O(1)$
或者

  1. 判断最小的数是否在第一个位置，若是则返回nums[0]；

  2. 否则，选取中间位置mid的数和right位置的数进行比较，若nums[mid] < nums[r]，说明最小的数在mid之前，right = mid；反之，令left = mid + 1；

  3. 重复进行，直到left >= right。

1
2
3
4
5
6
7
8
9
10
11
12
13
int findMin(int* nums, int numsSize){
    int left = 0, right = numsSize - 1, mid;
    if(nums[left] < nums[right])
        return nums[left];
    while(left < right) {
        mid = (left + right) / 2;
        if(nums[mid] > nums[right])
            left = mid + 1;   //nums[mid]已经比nums[right]大，故不再考虑nums[mid]
        else
            right = mid;      //nums[mid]比nums[right]小，表示nums[mid]可能是最小值
    }
    return nums[left];
}
Tags: 算法 LeetCode
← 最小公倍数&最大公因数 C语言一些要点总结 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏