[LeetCode] 153. Find Minimum in Rotated Sorted Array

【原题】 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

【解释】 给定一个旋转过的有序数组,要求返回该数组的最小值 【思路】 一个简单粗暴的方法就是O(n)查找,但是如果是这样的话,题目当中的有序就没有任何意义了。当在有序数组查找的时候,为了减少时间复杂度,可以很自然的想到二分查找,即使这里是部分有序。参见这里

public class Solution {
    public int findMin(int[] nums) {
      int left=0,right=nums.length-1;
        while(left<right){
            int mid=(left+right)/2;
            if(nums[mid]>nums[right])
                left=mid+1;//最小元素在右半部分
            else right=mid;//最小元素在左半部分,但mid也有可能是最小元素的index
        }
        return nums[left];
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能

Python数据处理(6)-pandas的数据结构

pandas是本系列后续内容所需要的第三方库,它是基于之前介绍的NumPy构建的,使得Python可以更加简单、方便地完成一系列数据分析工作。 ? 首先,使用下...

1958
来自专栏IMWeb前端团队

走进Sass殿堂

最近在学习sass,从sass新手的角度做一个简单的总结,总结的不对的地方期望各位大大们能多多指点,本文是针对sass3.4做的一个总结~ 一、变量篇 1.1 ...

17210
来自专栏机器学习和数学

[编程经验] Pandas入门(二)

上次介绍了Pandas的部分操作,包括创建Series,DataFrame以及基本索引,文件保存与读取等。今天我们介绍一下Pandas常用的其他功能。 首先我们...

3675
来自专栏北京马哥教育

Python爬虫基础知识:Python中的正则表达式教程

云豆贴心提醒,本文阅读时间7分钟 正则表达式在Python爬虫中的作用就像是老师点名时用的花名册一样,是必不可少的神兵利器。 一、 正则表达式基础 1.1.概...

2456
来自专栏博客园

IL指令详细表

512
来自专栏python读书笔记

《python算法教程》Day5 - DFS遍历图(邻接字典)DFS简介代码示例

这是《python算法教程》的第5篇读书笔记。这篇笔记的主要内容为运用DFS(深度优先搜索,depth first search)对图(邻接字典)进行遍历。 D...

38311
来自专栏Fundebug

JavaScript的值传递和引用传递

813
来自专栏机器学习算法与Python学习

Python:爬虫系列笔记(6) -- 正则化表达(推荐)

在前面我们已经搞定了怎样获取页面的内容,不过还差一步,这么多杂乱的代码夹杂文字我们怎样把它提取出来整理呢?下面就开始介绍一个十分强大的工具,正则表达式! 1.了...

3508
来自专栏liulun

Nim教程【八】

有序类型 值连续的枚举类型、整型、字符类型、布尔类型(还有这些类型的变种), 都可以称之为有序类型,Nim为有序类型提供了一系列特殊的方法 方法签名 方法...

1826
来自专栏深度学习自然语言处理

python科学计算之Pandas使用(一)

Pandas 是基于 NumPy 的一个非常好用的库,正如名字一样,人见人爱。之所以如此,就在于不论是读取、处理数据,用它都非常简单。

732

扫码关注云+社区