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.
Example 1:
Input: [3,4,5,1,2] Output: 1
Example 2:
Input: [4,5,6,7,0,1,2] Output: 0
题目大意:
找到旋转数组中的最小值。
解法:
按顺序寻找到数组中非递增的那个位置的数字,即是旋转数组中的最小值。
java:
class Solution { public int findMin(int[] nums) { int res=nums[0]; for(int i=0;i<nums.length-1;i++){ if(nums[i]>nums[i+1]){ res=nums[i+1]; break; } } return res; } }
采用二分查找寻找最小值。当数组中的第一个元素小于最后一个,说明该数组递增,直接返回第一个元素。否则查看数组中的中间元素,如果该元素比第一个元素要大的话,说明最小值在后半部分,要不然就在前半部分。
java:
class Solution { public int findMin(int[] nums) { int start=0,end=nums.length-1; while(start<end){ if(nums[start]<nums[end]) break; int mid=(start+end)/2; if(nums[start]<=nums[mid]) start=mid+1; else end=mid; } return nums[start]; } }