首页 > 代码库 > Leetcode: Find Minimum in Rotated Sorted Array
Leetcode: 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.
这道题跟Search in Rotated Sorted Array这道题很像，区别在于这道题不是找一个目标值，而是找最小值。所以与那道题的思路类似又有区别。类似在于同样是用binary search找目标区域，通过左边界和中间的大小关系来得到左边或者右边有序。区别在于这一次迭代不会存在找到target就终止的情况，iteration要走到 l > r 的情况才停止。所以这一次思路是确定中点哪一边有序之后，那一边的最小值就是最左边的元素。用这个元素尝试更新全局维护的最小值，然后迭代另一边。这样子每次可以截掉一半元素，所以最后复杂度等价于一个二分查找，是O(logn)，空间上只有四个变量维护二分和结果，所以是O(1)。
1 public class Solution { 2 public int findMin(int[] num) { 3 int l = 0; 4 int r = num.length - 1; 5 int min = Integer.MAX_VALUE; 6 while (l <= r) { 7 int m = (l + r) / 2; 8 if (num[m] < num[r]) { //[m, r] is sorted 9 if (num[m] < min) {10 min = num[m];11 }12 r = m - 1; // search [l, m-1] for next step13 }14 else { //[l, m] is sorted15 if (num[l] < min) {16 min = num[l];17 }18 l = m + 1; // search [m+1, r] for next step19 }20 }21 return min;22 }23 }
Leetcode: Find Minimum in Rotated Sorted Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。