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
相关推荐
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-0153 数组的乘积-除了-self-0238 从排序数组中删除重复项-0026 搜索旋转排序数组-0033 两个整数之和-0371 二和-0001 回溯 组合-和-0039 组合总和-ii-0040 电话号码的字母组合 ...
Leetcode扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...
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 II Median of Two Sorted Arrays H-Index II 暴力枚举法 Subsets Subsets II Permutations Permutations II Combinations Letter Combinations of a Phone Number 广度优先...
[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) ...
leetcode Phone interview: Implement hashmap Second minimum number in array given a sorted array, rotated at a pivot, find the maximum element what is encapsulation(封装) 大部分时间在问general ...