首页 > 代码库 > 153. Find Minimum in Rotated Sorted Array
153. Find Minimum in Rotated Sorted Array
Suppose an array sorted in ascending order 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.
根据题意遍历
public class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) return -1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < nums[i-1]) return nums[i];
}
return nums[0];
}
}
但是对于有序的数组还是用二分法效率比较高
这道题是Search in Rotated Sorted Array的扩展，区别就是现在不是找一个目标值了，而是在bst中找最小的元素。主要思路还是跟Search in Rotated Sorted Array差不多，还是通过左边界和中间的大小关系来得到左边或者右边有序的信息，如果左半边有序，那么左半边最小就是左边第一个元素，可以和当前最小相比取小的，然后走向右半边。否则，那么就是右半半边第一个元素，然后走向左半边。这样子每次可以截掉一半元素，所以最后复杂度等价于一个二分查找，是O(logn)，空间上只有四个变量维护二分和结果，所以是O(1)。代码如下：
public int findMin(int[] nums) {
if(nums == null || nums.length==0)
return 0;
int l = 0;
int r = nums.length-1;
int min = nums[0];
while(l + 1<r)
{
int m = (l+r)/2;
if(nums[l]<nums[m])
{
min = Math.min(nums[l],min);
l = m;
}
else if(nums[l]>nums[m])
{
min = Math.min(nums[m],min);
r = m;
}
else
{
l++;
}
}
min = Math.min(nums[r],min);
min = Math.min(nums[l],min);
return min;
}
有朋友可能注意到上面的实现还有第三种情况，就是左边界和中间是相等的情况，这道题目其实是不用发生的，因为元素没有重复，而Find Minimum in Rotated Sorted Array II这道题这考虑了元素重复的情况，这里只是为了算法更加一般性，就把那个情况也包含进来，有兴趣的朋友可以看看Find Minimum in Rotated Sorted Array II对重复元素的分析哈。
153. Find Minimum in Rotated Sorted Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。