图解「剑指Offer」之旋转数组的最小数字

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

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

示例 1:

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

示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

题目解析

最直接的方法是使用 暴力法:搜索整个数组,找到其中的最小元素,这样的时间复杂度是 O(N),其中 N 是给定数组的大小。

这道题目可以使用 二分搜索 的思想进行解决。

  • 找到数组的中间元素 mid。
  • 如果中间元素 > 数组第 low 个元素,则在 mid 右边搜索变化点。
  • 如果中间元素 < 数组第 high 个元素,则在 mid 左边搜索变化点。

动画描述

代码实现

//author:程序员小吴
class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            if (nums[low] < nums[high]) return nums[low];
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[high]){
               low = mid + 1; 
            } else{
               high = mid;
            } 
          }
        return nums[low];
    }
}

复杂度分析

  • 时间复杂度:O(logN) 。
  • 空间复杂度:O(1)。

知识点

数组、二分法、排序

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu)

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

原始发表时间:2019-08-27

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏蚂蚁开源社区

程序员生涯,这15个障碍让我“苦不堪言”

昨天必须得发布产品。用户争闹和咆哮某个缺失的功能。老板的老板说,我们最好迅速行动起来否则就炒我们的鱿鱼。感觉一切都有心无力。

10230
来自专栏葬爱家族

AndroidX

Google 2018 IO 大会推出了 Android新的扩展库 AndroidX,用于替换原来的 Android扩展库,按照官方文档说明 AndroidX ...

59250
来自专栏蚂蚁开源社区

前端关键技术点杂烩,这些你必须知道

这里总结一下 WEB 前端面试的常见问题,同时这些问题也是对一些基础的技术概念和思想的理解。对这些基本知识的掌握程度和深度决定了你的技术层级。高级工程师是必须掌...

10020
来自专栏Tech爬虫(公众号php_pachong)

PHP similar_text() 函数

注释:levenshtein() 函数比 similar_text() 函数更快。不过,similar_text() 函数通过更少的必需修改次数提供更精确的结果...

8430
来自专栏Tech爬虫(公众号php_pachong)

thinkphp的 getField用法总结

getField方法是ThinkPHP中用来获取字段值的方法,区别于select和find方法,通常仅用于获取个别字段的值。但是事实上并没有那么简单,该方法的用...

8810
来自专栏Tech爬虫(公众号php_pachong)

项目中常常出现的问题,答案在这里!

>如果是技术问题,接下去第二问,这个问题能解决吗?是否需要大牛一起来看一下。如果回答需要帮助,直接找技术一起看。

11320
来自专栏运维经验分享

Linux运维工程师必备的80个监控工具全集(上)

随着互联网行业的不断发展,各种监控工具多得不可胜数。这里列出网上最全的监控工具。让你可以拥有超过80种方式来管理你的机器。

21920
来自专栏Tech爬虫(公众号php_pachong)

PHP简单实现“相关文章”功能的方法

通常在做内容网站的时候,需要在每一篇文章中出现与该文章相关的文章列表。对于大多数人来说,使用的方法通常是:建立一个关键词列表,判断每篇文章包含有那些关键词,最后...

5010
来自专栏Tech爬虫(公众号php_pachong)

大型项目中的敏捷项目管理实践

现在软件领域三大俗,说的是敏捷、大数据、云,说的越多的往往也是处于成熟中,或者需求强调的,我所遇到的项目有幸几乎都触及到这些俗气的元素。

10420
来自专栏蚂蚁开源社区

关于爱情!诗人有情诗, 程序员有情码。

注释:「你说他很好,要和他一起生活。我转过身没舍得告诉你,我看到的未来不能同时容下他和你,但愿是我记不起,我原来从来没有见过你」

10920

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励