LintCode 题解丨微软面试题:寻找旋转排序数组中的最小值

简介: LintCode 题解丨微软面试题:寻找旋转排序数组中的最小值

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

在线评测地址:LintCode 领扣

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

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

算法流程

image.png

使用二分法来寻找最小值,如图所示可以帮助我们理解算法过程。
设置双指针​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) $。没有使用额外空间。
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];
}

}
更多题解参考:
九章算法 - 帮助更多中国人找到好工作,硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧

相关文章
|
6月前
|
算法
【数组相关面试题】LeetCode试题
【数组相关面试题】LeetCode试题
|
6月前
|
存储
力扣面试经典题之数组/字符串
力扣面试经典题之数组/字符串
51 0
|
6月前
|
算法 前端开发
经典面试题:扁平化嵌套数组
经典面试题:扁平化嵌套数组
42 0
|
3月前
|
C语言
【Amazon 面试题1】一个数组,里面得数出现的次数是偶数次,只有一个数出现的次数是奇数次,找出那个出现奇数次的数
本文介绍了解决Amazon面试题的一种方法,即在一个所有数字出现次数都是偶数,除了一个数字出现奇数次的数组中,利用异或运算的性质找出出现奇数次的数字,并提供了C语言实现的代码示例。
61 1
|
3月前
|
Java
Java 基础语法-面试题(54-63道)(数组+类+包)
Java 基础语法-面试题(54-63道)(数组+类+包)
41 16
|
4月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
5月前
|
开发框架 .NET
技术好文共享:面试题:找出数组中只出现一次的2个数(异或的巧妙应用)(出现3次)
技术好文共享:面试题:找出数组中只出现一次的2个数(异或的巧妙应用)(出现3次)
|
5月前
|
数据采集 算法 数据挖掘
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
|
6月前
|
C++
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
|
6月前
|
算法 C++
【一刷《剑指Offer》】面试题 8:旋转数组的最小数字
【一刷《剑指Offer》】面试题 8:旋转数组的最小数字