V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
牛客网
zzzrf
V2EX  ›  推广

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

  •  
  •   zzzrf · 53 天前 · 2928 次点击
    这是一个创建于 53 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    在线做题地址

    样例 1:

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

    样例 2:

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

    解题思路

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

    算法流程

    1

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

    更多题解参考

    21 条回复    2020-09-08 14:07:58 +08:00
    ErwinCheung
        1
    ErwinCheung   53 天前
    真大佬果然清一色的 java
    yuruizhe
        2
    yuruizhe   53 天前
    挺有意思,不错
    bintianbaihua
        3
    bintianbaihua   52 天前
    liuxu
        4
    liuxu   52 天前
    字很可爱,不知道缺不缺男朋...哦不,我是说老哥拆解分析的很到位
    SimonOne
        5
    SimonOne   52 天前
    大佬的算法流程图用的什么软件手写的呀?
    zzzrf
        6
    zzzrf   52 天前
    @liuxu ssfd
    ljp12008
        7
    ljp12008   52 天前
    留个爪印,话说楼主的字体真可爱
    lewis89
        8
    lewis89   52 天前
    @zzzrf #6 请说能用来 google 的话
    ai277014717
        9
    ai277014717   52 天前 via Android   ❤️ 4
    面试遇到过。记住了一句话。凡是有序的都可以用二分法。
    tongyang
        10
    tongyang   52 天前
    leetcode 原题吧
    zzzrf
        11
    zzzrf   52 天前
    @ai277014717 GOOD JOB
    qinglingyue
        12
    qinglingyue   52 天前
    力扣刚做过,这字真是爱了爱了~
    DoubleFlyme
        13
    DoubleFlyme   52 天前
    歪楼问一下这字是用什么写的
    zzzrf
        14
    zzzrf   52 天前   ❤️ 1
    @DoubleFlyme ipad 做的
    Seazouhp
        15
    Seazouhp   52 天前
    果然又是九章算法的软广,谁艾特一下管理员
    fishCatcher
        16
    fishCatcher   52 天前 via iPhone
    @ai277014717 不一定哦,很多要用滑动窗口或者双指针
    framlog
        17
    framlog   52 天前
    leetcode 原题+1
    norbread2003
        18
    norbread2003   52 天前
    哇大佬的字,好酸
    fuxiuyin
        19
    fuxiuyin   52 天前
    然后还有升级版,切两刀,分成 ABC 三段,AC 段交换变成 CBA,实现查找算法。
    maxiaoam
        20
    maxiaoam   52 天前   ❤️ 1
    @Livid 推广
    banishee
        21
    banishee   51 天前
    话说,楼主用的 ipad 什么软件诶
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4697 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 18ms · UTC 02:40 · PVG 10:40 · LAX 19:40 · JFK 22:40
    ♥ Do have faith in what you're doing.