首页 > 代码库 > leetcode 153: Find Minimum in Rotated Sorted Array
leetcode 153: Find Minimum in Rotated Sorted Array
Find Minimum in Rotated Sorted Array
Total Accepted: 21207 Total Submissions: 65855Suppose 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.
[分析]
二分法, 如果 num[mid] 和相邻elements 不是ordered, 最小值可得. 否则, 查看 low 和 high 是否有序, 跳到无顺序的一半.[注意事项]
NONE
[CODE]
public class Solution { public int findMin(int[] num) { if(num==null || num.length < 1) return 0; // ask interviewer which value should return: Integer.MIN_VALUE or throw a Exception. int low = 0, high = num.length-1; while(low < high) { int mid = low + (high-low)/2; int x = num[mid]; if( mid != num.length-1 && x>num[mid+1]){ return num[mid+1]; } else if(num[mid] < num[low]) { high = mid; } else if(num[mid] > num[high]) { low = mid; } else { return num[low]; } } return num[low]; } }
leetcode 153: Find Minimum in Rotated Sorted Array
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。