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

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之二进制中1的个数(九度OJ1513)

题目描述: 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 输入: 输入可能包含多个测试样例。 对于每个输入文件,第一行输入一个整数T,代表测...

1819
来自专栏WD学习记录

牛客网 数字游戏

小易邀请你玩一个数字游戏,小易给你一系列的整数。你们俩使用这些整数玩游戏。每次小易会任意说一个数字出来,然后你需要从这一系列数字中选取一部分出来让它们的和等于小...

731
来自专栏CaiRui

Python 文件和异常

一、从文件中读取数据 #!/usr/bin/env python with open('pi') as file_object: contents =...

19910
来自专栏青青天空树

2034-人见人爱A-B(c++实现)

参加过上个月月赛的同学一定还记得其中的一个最简单的题目,就是{A}+{B},那个题目求的是两个集合的并集,今天我们这个A-B求的是两个集合的差,就是做集合的减法...

732
来自专栏五分钟学算法

每天一算:Two Sum

713
来自专栏技术碎碎念

LeetCode-15-3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b ...

35511
来自专栏Fish

内存对齐(Memory Alignment)

最近读文档,发现对内存对齐的概念不太明白。 内存对齐的原则: 数据成员对齐规则:结构(struct)(或联合(union))的数据成员,第一个数据成员放在o...

17210
来自专栏WD学习记录

牛客网 二进制中1的个数

642
来自专栏Crossin的编程教室

【Python 第66课】列表综合

大家假期过得可好?今天来讲讲 Python 里一个我非常喜欢的特性--列表综合(List Comprehension)。所谓列表综合,就是通过一个已有的列表生成...

3328
来自专栏Bingo的深度学习杂货店

Q792 Number of Matching Subsequences

Given string S and a dictionary of words words, find the number of words[i] that...

673

扫码关注云+社区