`

Find Minimum in Rotated Sorted Array

阅读更多
Suppose a sorted array 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), 因为这是有序数组进行了旋转,我们可以考虑二分查找法,这样时间复杂度为O(logn)。二分查找的关键在于找到一个条件进行判断,然后可以省略掉一半元素。在这这题目中,我们通过中间元素与最右边的元素进行比较,如果中间元素array[m] > array[right],那么说明做部分为有序的,并且最小值肯定在右半部分,这是我们只需要移动左指针,指向m + 1位置,然后对后半部分进行搜索。如果中间元素小于最右边元素,说明最小值在左部分,这是让右指针指向m位置,因为m位置的元素可能为最小值,然后查找左半部分。代码如下:
public class Solution {
    public int findMin(int[] nums) {
        if(nums == null || nums.length == 0) return -1;
        int l = 0; 
        int r = nums.length - 1;
        while(l < r) {
            int m = l + (r - l) / 2;
            if(nums[m] > nums[r]) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return nums[l];
    }
}
0
0
分享到:
评论

相关推荐

    lrucacheleetcode-Coding-Interview:编程面试

    Find Minimum In Rotated Sorted Array Find Minimum In Rotated Sorted Array II Search In Rotated Sorted Array Search In Rotated Sorted Array II 二分搜索/有序矩阵 Kth Smallest Element In A Sorted Matrix ...

    leetcode分类-interview:面试基础算法

    sorted array 81: search in rotated sorted array ii 153: find minimum in rotated sorted array 162: find peak element 34: find first and last position of element in sorted array 300: longest increasing ...

    leetcode写题闪退-LeetCode:leetcodeOJ

    对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated Sorted Array这两道题目,我也是醉了。。。代码完全一样的不说,题目还都特别傻逼。 Maximum Product Subarray 动态规划,类似于求最大...

    cpp-算法精粹

    Find Minimum in Rotated Sorted Array II Median of Two Sorted Arrays H-Index II 暴力枚举法 Subsets Subsets II Permutations Permutations II Combinations Letter Combinations of a Phone Number 广度优先...

    LeetCode C++全解

    Find Minimum in Rotated Sorted Array viii. Largest Rectangle in Histogram ix. Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. ...

    扔鸡蛋leetcode-LeetCode-Note-Mary:玛丽的leetcode笔记本

    扔鸡蛋 leetcode LeetCode-Note-Mary Mary's leetcode notebook The order of problems ...in ...Minimum in Rotated Sorted Array(寻找旋转排序数组中的最小值) 2020/12/09 300. Longest Increasing

    Leetcode扑克-coding-interviews:编码面试

    Minimum in Rotated Sorted Array 斐波那契数列 509. Fibonacci Number 跳台阶 70. Climbing Stairs 变态跳台阶 矩形覆盖 二进制中1的个数 191. Number of 1 Bits 数值的整数次方 50. Pow(x, n) 调整数组顺序使奇数...

    javalruleetcode-leetcode:这是Java写的leetcode

    [Java](./src/Find minimum in Rotated Sorted Array II/Solution.java) 2014/10/20 难的 [Java](./src/在旋转排序数组中查找最小值/Solution.java) 2014/10/15 中等的 [Java](./src/最大乘积子阵列/Solution.java) ...

    leetcodelintcode差异-leetcode-python:leetcode-python

    Find Minimum in Rotated Sorted Array 双指针 题目 Solution Tag LintCode 604. Window Sum LeetCode 283. Moves Zeroes Array、Two Pointers Array、Two Pointers LeetCode 120. Triangle LintCode 382. Triangle ...

    Find-Minimum-in-Rotated-Sorted-Array-II

    查找最小的旋转排序数组II 假设以升序排序的长度为n的数组在1到n之间旋转。 例如,数组nums = [0,1,4,4,5,6,7]可能变为: [4,5,6,7,0,1,4]如果旋转了4次。 [0,1,4,4,5,6,7]如果已旋转7次。 请注意,旋转数组[a ...

    leetcode变形词-Leetcode-Data-Structures-and-Algorithms:该存储库包含基于数据结构和算法的编码问

    leetcode变形词 :fire: Leetcode / 数据结构和算法 ...in_Rotated_Sorted_Array.java) :pushpin: 数组 :pushpin: 比赛 提交 2020 年 Google Code Jam 资格赛 提交 Google Hash Code 2020 在线资格赛

    lrucacheleetcode-leetcode-in-go:leetcode-in-go

    find-minimum-in-rotated-sorted-array-0153 数组的乘积-除了-self-0238 从排序数组中删除重复项-0026 搜索旋转排序数组-0033 两个整数之和-0371 二和-0001 回溯 组合-和-0039 组合总和-ii-0040 电话号码的字母组合 ...

    javalruleetcode-shy:害羞的

    minimum number in array given a sorted array, rotated at a pivot, find the maximum element what is encapsulation(封装) 大部分时间在问general behavior question。 比如要是组里有人不工作怎么办, 工作如果...

    FlexGraphics_V_1.79_D4-XE10.2_Downloadly.ir

    - ADD: In the module FlexUtils added the constant BooleanWords - an array containing the words 'false' and 'true' for saving/reading TBoolProp. - ADD: In the module FlexUtils added the function ...

Global site tag (gtag.js) - Google Analytics