`

LeetCode 153 - 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.

Solution 1:

public int findMin(int[] num) {
    int start = 0, end = num.length-1;
    int min = num[0];
    while(start <= end) {
        int mid = (start + end) / 2;
        if(num[mid] <= num[end]) { // 7 0 1 2 4 5 6, min位于上升沿左侧
            end = mid - 1;
        } else { // 4 5 6 7 0 1 2, min位于左侧上升沿与右侧上升沿之间
            start = mid + 1;
        }
        min = Math.min(min, num[mid]);
    } 
    return min;
}

 

Solution 2:

这是我所见到的最简单的解法了,源自StackOverFlow。(注:这个方法在有重复元素的情况下无效)

public int findMin(int[] num) {
    int l = 0, h = num.length-1;
    while(num[l] > num[h]) {
        int m = (l + h) / 2;
        if(num[m] > num[h]) { // 4 5 6 7 0 1 2, min位于左侧上升沿与右侧上升沿之间
            l = m + 1;
        } else { // 7 0 1 2 4 5 6, min位于上升沿左侧
            h = m;
        }
    } 
    return num[l];
}

 

下面的版本是能够处理有重复元素的情况:

public int findMin(int[] num) {  
    int l = 0, h = num.length-1;  
    while(l < h && num[l] >= num[h]) {  
        int m = (l + h) / 2;  
        if(num[m] > num[h]) { // 4 5 6 7 0 1 2, min位于左侧上升沿与右侧上升沿之间  
            l = m + 1;  
        } else if(num[m] < num[h]) { // 7 0 1 2 4 5 6, min位于上升沿左侧  
            h = m;  
        } else {
            l++;
        }
    }
    return num[l];  
} 

 

Reference:

http://stackoverflow.com/questions/8532833/find-smallest-number-in-sorted-rotatable-array

分享到:
评论

相关推荐

    python-leetcode题解之153-Find-Minimum-in-Rotated-Sorted-Array.py

    python python_leetcode题解之153_Find_Minimum_in_Rotated_Sorted_Array.py

    python-leetcode题解之154-Find-Minimum-in-Rotated-Sorted-Array-II.py

    python python_leetcode题解之154_Find_Minimum_in_Rotated_Sorted_Array_II.py

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

    leetcode 分类 :person_running::person_running::person_running: 算法 :person_running::person_running::person_running:‍ 实践&理论 :books: :ear: :television: Binary Search(二分查找) easy 69: 278: 35: ...

    扔鸡蛋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

    lrucacheleetcode-Coding-Interview:编程面试

    leetcode Coding-Interview A repo for popular coding interview problems mainly from Leetcode. 二分搜索/有序数组旋转 Find Minimum In Rotated Sorted Array Find Minimum In Rotated Sorted Array II Search ...

    算法刷题笔记leetcode/lintcode

    - Find Minimum in Rotated Sorted Array II(在旋转排序数组中寻找最小值II) - Median(中位数) ### 分析与总结 该文档是针对LeetCode和LintCode平台上的算法题目的整理与解答,主要分为两大部分: 1. **...

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

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

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

    Leetcode扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...

    leetcode卡-Array-LeetCode-Solution:数组-LeetCode-解决方案

    如"寻找旋转排序数组中的最小值"(Find Minimum in Rotated Sorted Array)。 4. **滑动窗口**:在给定大小的窗口内处理数组元素,常用于求解最大/最小值、频率统计等问题。如"最宽的水平条"(Largest Rectangle in...

    leetcode写题闪退-LeetCode:leetcodeOJ

    leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...

    leetcodelintcode差异-leetcode-python:leetcode-python

    leetcode lintcode差异 leetcode-python 九章算法基础班 二分 题目 地址 153. Find Minimum in Rotated Sorted Array 双指针 题目 Solution Tag LintCode 604. Window Sum LeetCode 283. Moves Zeroes Array、Two ...

    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-Data-Structures-and-Algorithms:该存储库包含基于数据结构和算法的编码问

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

    Leetcode题目+解析+思路+答案.pdf

    - **Find Minimum in Rotated Sorted Array**:在一个旋转了的有序数组中找到最小值。 - **Largest Rectangle in Histogram**:在直方图中找到最大的矩形面积。 - **Maximal Rectangle**:在二维矩阵中找到最大的...

    python-leetcode面试题解之第153题寻找旋转排序数组中的最小值-题解.zip

    在本题解中,我们将深入探讨Python编程语言在解决LeetCode第153题——"寻找旋转排序数组中的最小值"(Find Minimum in Rotated Sorted Array)时的应用。LeetCode是一系列面向程序员的在线编程挑战平台,对于求职...

    Leetcode book刷题必备

    50. Find Minimum in Rotated Sorted Array II – With Duplicates:与上题类似,但是数组中可能存在重复元素。 以上就是该文件中提及的知识点,都是与编程面试密切相关的经典算法和数据结构题目。通过学习和练习...

    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) ...

    php-leetcode题解之寻找旋转排序数组中的最小值.zip

    在LeetCode中,这个问题通常被称为“寻找旋转排序数组中的最小值”(Find Minimum in Rotated Sorted Array)。解决这个问题,我们可以利用数组的两个关键特性:一部分是升序排列,另一部分是降序排列。由于数组是...

    CleanCodeHandbook_v1.0.3

    - Find Minimum in Sorted Rotated Array(在排序旋转数组中查找最小值) 从文件中提取的信息点可以看出,"CleanCodeHandbook_v1.0.3" 是一个专注于指导如何编写清晰且简洁代码的书籍,尤其侧重于常见的编程面试题...

Global site tag (gtag.js) - Google Analytics