[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 条评论
登录 后参与评论

相关文章

来自专栏芋道源码1024

Java 函数式编程和 lambda 表达式

函数式编程更多时候是一种编程的思维方式,是种方法论。函数式与命令式编程的区别主要在于:函数式编程是告诉代码你要做什么,而命令式编程则是告诉代码要怎么做。说白了,...

661
来自专栏技术专栏

python3入门与实践(六):函数式编程

一定程度下lambda可以替换命令式编程的函数,reduce可以替换命令式编程的循环

891
来自专栏风口上的猪的文章

.NET面试题系列[11] - IEnumerable<T>的派生类

ICollection<T>继承IEnumerable<T>。在其基础上,增加了Add,Remove等方法,可以修改集合的内容。IEnumerable<T>的直...

842
来自专栏成猿之路

Java面试题-基础篇一

1053
来自专栏北京马哥教育

从Zero到Hero,一文掌握Python关键代码

本文整体梳理了 Python 的基本语法与使用方法,并重点介绍了对机器学习十分重要且常见的语法,如基本的条件、循环语句,基本的列表和字典等数据结构,此外还介绍...

2927
来自专栏C++

python笔记:#005#算数运算符

1272
来自专栏java学习

面试题11(谈谈final、finally、finalize的区别)

考点:考察求职者对这3个java关键字的理解和区分 出现频率:★★★★ 【面试题解析】带有 final修饰符的类是不可派生的。在Java核心APⅠ中,有许多应用...

37210
来自专栏BestSDK

封装、私有,一文掌握Python关键代码

首先,什么是 Python?根据 Python 创建者 Guido van Rossum 所言,Python 是一种高级编程语言,其设计的核心理念是代码的易读性...

3333
来自专栏java学习

重要通知!小编出新的Java练习题已经公布答案了!!!

一、选择题和问答题 1、在一个java原文件中,import, class, package语句的顺序是(D)。 A. import classpackage ...

3728
来自专栏CDA数据分析师

Python 面试中8个必考问题

? 翻译 everfighting 原文链接:https://www.toptal.com/python/interview-questions Q1、下...

3489

扫码关注云+社区