专栏首页五分钟学算法一道腾讯算法题,拿好不谢~

一道腾讯算法题,拿好不谢~

大家好,我是程序员吴师兄。

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题11.旋转数组的最小数字。根据统计,在腾讯的算法面试环节出现频率较高,属于简单中等难度。

题目链接:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

一、题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组[3,4,5,1,2][1,2,3,4,5] 的一个旋转,该数组的最小值为 1。

示例 1:

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

示例 2:

输入:[2,2,2,0,1]
输出:0

二、题目解析

这道题最直观的解法是 从头到尾遍历数组一次,轻轻松松就能找出最小的元素。

这种思路的时间复杂度显然是 O(n)

很显然,这种做法 没有利用输入的旋转数组的特性,所以在面试环节面试官肯定会问你:还能优化一下吗?

一般的,O(n) 复杂度的优化我们都是往 二分查找 这个思路上去考虑的。

设置 start, end 指针分别指向 numbers 数组左右两端,取它们的中点 mid = (start + end ) / 2,然后将 numbers[mid]numbers[end] 进行对比:

1、当 numbers[mid] > numbers[end]

此时,mid 在 左排序数组 中,而旋转点 x 一定在 [ mid + 1,end ] 闭区间内,所以接下来的操作是在 [ mid + 1,end ] 区间内寻找旋转点,相应的,改变 start 的值为 mid + 1。

2、numbers[mid] < numbers[end]

此时,mid 在 右排序数组 中,而旋转点 x 一定在 [ start,mid ] 闭区间内,所以接下来的操作是在 [ start,mid ] 区间内寻找旋转点,相应的,改变 end 的值为 mid 。

3、numbers[mid] = numbers[end]

三、动画描述

四、图片描述

五、参考代码

class Solution {
    public int minArray(int[] numbers) {
        //设置 start, end 指针分别指向 numbers 数组左右两端
        int start = 0, end = numbers.length - 1;

        //循环判断处理,直到找到结果
        while (start < end) {

            // mid 为中点(这里向下取整,比如 ( 2 + 7 )/ 2 = 4 )
            int mid = (start + end) / 2;

            //当 mid 点所在元素大于数组末端的元素时,这意味着 [start , mid] 是有序的数组
            if (numbers[mid] > numbers[end]){

                // 所以旋转点在 [ mid + 1, end ] 区间里面 ,更新 start 的位置为 mid + 1
                start = mid + 1;

            }else if (numbers[mid] < numbers[end]){

                // 当 mid 点所在元素小于数组开始端的元素时,这意味着 [mid , end] 是有序的数组
                // 所以旋转点在 [ start, mid ] 区间里面 ,更新 end 的位置为 mid 
                end = mid;

                //思考题?:为什么 start 是更新为 mid + 1,而 end 却是更新为 mid

            }else{

                //此时,出现了 numbers[mid] = numbers[end] 的情况,无法判断 
                //    [ start , mid ]  为有序数组区间
                //  还是  [ mid , end ]  为有序数组区间
                //  比如: [1, 0, 1, 1, 1] 和  [1, 1, 1, 0, 1]
                //  所以这里采取遍历的方式
                return findMin(numbers,start,end);

            }
        }
        return numbers[start];
    }


     public int findMin(int[] numbers,int start,int end){

        int result = numbers[start];

        for(int i = start;i <= end;i++){

            if (numbers[i] < result) {
                result = numbers[i];
            }
        }
        return result;
    }
}

六、复杂度分析

时间复杂度

时间复杂度为 O(log2N)。

空间复杂度

空间复杂度为 O(1)。

七、相关标签

  • 二分查找
  • 数组

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员吴师兄

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 懵逼树上懵逼果:学习二分搜索树

    我们通过两组添加元素,三组删除元素,一组查找元素的操作来理解二叉查找树的属性性质。

    五分钟学算法
  • LeetCode 图解 | 540. 有序数组中的单一元素

    题目来源于 LeetCode 上第 540 号问题:有序数组中的单一元素。题目难度为中等,目前通过率60.2%。

    五分钟学算法
  • 每天一算:二叉树的中序遍历

    下面这种写法使用了一个辅助结点p,这种写法其实可以看作是一个模版,对应的还有前序和后序的模版写法,形式很统一,方便于记忆。上篇更新前序的和后面要更新后序文章中都...

    五分钟学算法
  • java判断字符是否唯一

    ASCII码字符个数为128个,位运算没有128的变量,这里参考了评论区yuruiyin的办法,使用两个64位的long变量。 基础想法是用一位二进制数表示某...

    崔笑颜
  • Harbor介绍及我们的改造

    说明:我们是基于Harbor V0.4.1进行分析和改造的。 ##为什么不是直接使用Registry V2,而选用Harbor? ###可以用Harbor做以下...

    Walton
  • Sublime text3 将代码复制为RTF或HTML的方法

    添加下面url: https://github.com/n1k0/SublimeHighlight/tree/python3

    飞奔去旅行
  • Android使用token维持登陆状态

    token(令牌)是一串唯一的字符串,通常由服务端生成,在注册完成时返回给客户端,用来标识此用户,客户端将此字符串存储在本地。在以后的网络请求时,客户端先查询本...

    用户1665735
  • dubbo学习之本地存根实践

    今天主要学习并实践dubbo的本地存根stub机制。首先了解一下官网文档对本地存根的介绍:

    沁溪源
  • 吴晓波:自由与理想

    用户1756920
  • 我是如何用10行代码搬运目标图片的?

    嗯呢,你没看错,就是教你把一个路径下的所有目标图片搬运到制定路径下。有读者说:小詹你忽悠人吧,要搬运目标图片复制粘贴不就好了嘛,要什么代码,搬砖脑子秀逗了?

    小小詹同学

扫码关注云+社区

领取腾讯云代金券