首页 > 代码库 > 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?
前面那道题：Find Minimum in Rotated Sorted Array, 唯一的区别是这道题目中元素会有重复的情况出现。不过正是因为这个条件的出现，影响到了算法的时间复杂度。原来我们是依靠中间和边缘元素的大小关系，来判断哪一半是不受rotate影响，仍然有序的。而现在因为重复的出现，如果我们遇到中间和边缘相等的情况，我们就无法判断哪边有序，因为哪边都有可能有序。假设原数组是{1,2,3,3,3,3,3}，那么旋转之后有可能是{3,3,3,3,1,2,3}，或者{3,1,2,3,3,3,3}，这样的我们判断左边缘和中心的时候都是3，我们并不知道应该截掉哪一半。解决的办法只能是对边缘移动一步，直到边缘和中间不在相等或者相遇，这就导致了会有不能切去一半的可能。所以最坏情况就会出现每次移动一步，总共移动n此，算法的时间复杂度变成O(n)。
1 public class Solution { 2 public int findMin(int[] num) { 3 int l = 0; 4 int r = num.length - 1; 5 int minval = Integer.MAX_VALUE; 6 while (l <= r) { 7 int m = (l + r) / 2; 8 if (num[m] < num[r]) { 9 minval = Math.min(num[m], minval);10 r = m - 1;11 }12 else if (num[m] > num[r]) {13 minval = Math.min(num[l], minval);14 l = m + 1;15 }16 else if (m == r){17 minval = Math.min(num[m], minval);18 r = m - 1;19 }20 else {21 r--;22 }23 }24 return minval;25 }26 }
Leetcode: Find Minimum in Rotated Sorted Array II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。