本文共 997 字,大约阅读时间需要 3 分钟。
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
jiuzhang solution: Binary Search
可以将数组分成两部分,需要寻找的值是O部分的第一个值。而O部分的判断条件是小于等于最后一个数。因此这道题可以通过与最后一个值进行判断,不满足的扔掉,满足的往前推进缩小范围6 54-------------- 3 2 1X X X O O O
class Solution { public int findMin(int[] nums) { if (nums == null || nums.length == 0) { return -1; } int start = 0, end = nums.length - 1; while(start + 1 < end) { int mid = start + (end - start) / 2; if(nums[mid] > nums[end]) { start = mid + 1; } else { end = mid; } } return Math.min(nums[end], nums[start]); }}
Follow UP: 如果有重复的数,是否仍然能够O(logn)
证明:不行,特殊例子[1,1,1,1,1,0,1,1,1],一堆1中有一个0转载地址:http://rkqvb.baihongyu.com/