程序媛小姐姐分享微软面试真题:寻找旋转排序数组中的最小值

760 阅读1分钟

假设一个排好序的数组在其某一未知点发生了旋转(比如 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2 )。你需要找到其中最小的元素。

在线评测地址:www.lintcode.com/problem/fin…

样例 1:

输入:[4, 5, 6, 7, 0, 1, 2]
输出:0
解释:
数组中的最小值为 0

样例 2:

输入:[2,1]
输出:1
解释:
数组中的最小值为 1

解题思路

  • 最直接的是暴力解法,搜索整个数组找到最小元素,时间复杂度为 O(n)。
  • 我们可以旋转数组的特性,用改进后的二分查找来解决,时间复杂度为 O(logn)。 算法流程

image

  • 使用二分法来寻找最小值,如图所示可以帮助我们理解算法过程。
  • 设置双指针 left 和 right 指向数组 nums 两端。
  • 第一次分类讨论:比较 nums[left]和 nums[right]
    • 如果 nums[left] < nums[right],说明数组没有旋转过,仍然是升序排列。我们直接 return nums[left]。
    • 反之,说明数组非单调,进入到第二次分类讨论。
  • 第二次分类讨论:比较 nums[left]和 nums[mid],其中 mid 是二分中点。
    • 如果 nums[left] > nums[mid],可以证明此时数组右半边是升序的,那我们就不用考虑右半边了。最小值一定在[left, mid]间,令 right = mid 。
    • 如果 nums[left] <= nums[mid],可以证明此时数组左半边是升序的,于是我们不需要考虑左半边。最小值一定在(mid, right]间,令 left = mid + 1 。
  • 直到 left == right 时,此时指向的就是最小值,return nums[left]。

等效方法

  • 上述算法中,第二次分类讨论我们比较的是 nums[left]和 nums[mid]的大小关系,其实比较 nums[right]和 nums[mid]的大小也是一样的。
    • nums[left] > nums[mid],等效于 nums[mid] < nums[right]
    • nums[left] <= nums[mid],等效于 nums[mid] > nums[right]
  • 有兴趣可以证明一下。代码如何实现,看个人的 preference 啦。

复杂度分析

  • 时间复杂度: O(log(n)),n 为 nums 的长度。同二分查找的时间复杂度。
  • 空间复杂度: O(1)O(1) 。没有使用额外空间。
public class Solution {
    /**
     * @param nums: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        // 二分法
        while (left < right){
            // 最小值在 left
            if (nums[left] < nums[right]){
                return nums[left];
            }
            int mid = left + (right - left) / 2;
            // 最小值在[left, mid]
            if (nums[left] > nums[mid]){
                right = mid;
            }
            // 最小值在(mid, right]
            else{
                left = mid + 1;
            }
        }
        return nums[left];
    }
}

更多题解参考:www.jiuzhang.com/solution/fi…