首页 > 代码库 > Leetcode-Find Minimum in Rotated Sorted Array II
Leetcode-Find Minimum in Rotated Sorted Array II
Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?Would this affect the run-time complexity? How and why?
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.
The array may contain duplicates.
Analysis:
For this problem, if we find that num[start]==num[mid]==num[end], we have to search both the left part and right part, because we do not know the min value is in which part. For example: 4 4 4 4 4 1 2 3 4 and 4 1 2 3 4 4 4 4 4.
Solution:
1 public class Solution { 2 public int findMin(int[] num) { 3 if (num.length==0) return -1; 4 int start = 0, end = num.length-1; 5 int min = findMinRecur(num,start,end); 6 return min; 7 } 8 9 //NOTE: We need to consider the ending case that start==end, this happens when there is only one element in the array!10 public int findMinRecur(int[] num, int start, int end){11 if (start==end-1 || start==end){12 if (num[start]<num[end]) return num[start];13 else return num[end];14 }15 16 int mid = (start+end)/2;17 int min = Integer.MAX_VALUE;18 if (num[mid]<num[start]){19 min = findMinRecur(num,start,mid);20 return min;21 }22 23 if (num[mid]>num[end]){24 start = mid;25 min = findMinRecur(num,mid,end);26 return min;27 }28 29 if (num[mid]==num[start] && num[mid]==num[end]){30 int min1 = findMinRecur(num,start,mid);31 int min2 = findMinRecur(num,mid,end);32 if (min1<min2) return min1;33 else return min2;34 }35 36 if (num[start]>num[end]) return num[end];37 else return num[start];38 }39 }
Leetcode-Find Minimum in Rotated Sorted Array II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。