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

数据结构
数据结构, 高频面试题总结

题目详情

假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。

你需要找到其中最小的元素。

你可以假设数组中不存在重复的元素。

思路：

  • 顺序遍历，找到逆序对即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    /**
     * @param nums: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0)
            return -1;
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i-1])
                return nums[i];
        }
        
        return nums[0];
    }
}

暴力解法虽然简单，但时间复杂度较高，因此我们寻找效率更高的二分查找法解决此类问题。

二分查找解

思路：

  • 以数组最后一个最为target，寻找数组中第一个小于target的值
  • 与常规的排序数组不同：
    • 当nums[mid] > target时，我们可以知道最小值在mid的右边
    • 当nums[mid] < target时，我们可以知道最小值在mid的左边
      如下图所示：
      二分查找思路示意图

因此，我们可以得到如下代码：

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
public class Solution {
    /**
     * @param nums: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0)
            return -1;
        
        int start = 0;
        int end = nums.length - 1;
        int mid;
        int target = nums[end];
        //找到第一个小于target的数
        while (start <= end) {
            mid = start + ((end - start) >> 1);
            //如果nums[mid] > target , 则最小值在mid左边
            if (nums[mid] > target)
                start = mid + 1;
            //如果nums[mid] <= target, 则最小值在mid右边
            if (nums[mid] <= target)
                end = mid - 1;
        }
        
        return nums[end + 1];
        
    }
}
Compartir Comentarios