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
相关推荐
javascript js_leetcode题解之153-find-minimum-in-rotated-sorted-array.js
javascript js_leetcode题解之154-find-minimum-in-rotated-sorted-array-ii.js
python python_leetcode题解之153_Find_Minimum_in_Rotated_Sorted_Array.py
python python_leetcode题解之154_Find_Minimum_in_Rotated_Sorted_Array_II.py
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 Mary's leetcode notebook The order of problems ...in ...Minimum in Rotated Sorted Array(寻找旋转排序数组中的最小值) 2020/12/09 300. Longest Increasing
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 ...
- Find Minimum in Rotated Sorted Array II(在旋转排序数组中寻找最小值II) - Median(中位数) ### 分析与总结 该文档是针对LeetCode和LintCode平台上的算法题目的整理与解答,主要分为两大部分: 1. **...
find-minimum-in-rotated-sorted-array-0153 数组的乘积-除了-self-0238 从排序数组中删除重复项-0026 搜索旋转排序数组-0033 两个整数之和-0371 二和-0001 回溯 组合-和-0039 组合总和-ii-0040 电话号码的字母组合 ...
Leetcode扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...
如"寻找旋转排序数组中的最小值"(Find Minimum in Rotated Sorted Array)。 4. **滑动窗口**:在给定大小的窗口内处理数组元素,常用于求解最大/最小值、频率统计等问题。如"最宽的水平条"(Largest Rectangle in...
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
leetcode lintcode差异 leetcode-python 九章算法基础班 二分 题目 地址 153. Find Minimum in Rotated Sorted Array 双指针 题目 Solution Tag LintCode 604. Window Sum LeetCode 283. Moves Zeroes Array、Two ...
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变形词 :fire: Leetcode / 数据结构和算法 ...in_Rotated_Sorted_Array.java) :pushpin: 数组 :pushpin: 比赛 提交 2020 年 Google Code Jam 资格赛 提交 Google Hash Code 2020 在线资格赛
- **Find Minimum in Rotated Sorted Array**:在一个旋转了的有序数组中找到最小值。 - **Largest Rectangle in Histogram**:在直方图中找到最大的矩形面积。 - **Maximal Rectangle**:在二维矩阵中找到最大的...
在本题解中,我们将深入探讨Python编程语言在解决LeetCode第153题——"寻找旋转排序数组中的最小值"(Find Minimum in Rotated Sorted Array)时的应用。LeetCode是一系列面向程序员的在线编程挑战平台,对于求职...
50. Find Minimum in Rotated Sorted Array II – With Duplicates:与上题类似,但是数组中可能存在重复元素。 以上就是该文件中提及的知识点,都是与编程面试密切相关的经典算法和数据结构题目。通过学习和练习...
[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) ...