Obviously this question can be solved within O(n) time by traversing the whole array and looking for the position i that satisfies nums[i] < nums[i - 1]. However, we haven’t make use of the sorted feature of the array yet. By take sorted into consideration, we can use a slightly changed binary search way and reduce the runtime to O(logn).
Noticing that the input array is sorted in ascending order and is rotated.
Analyis: The input array is sorted in ascending order and is rotated, this leads to 2 possible conditions: The input array is rotated right k positions wherek % nums.length = 0. Under this condition, the input array is actually equal to an unroated one. Thus the minimum is the simply the first element. The input array is rotated right k positions where k % nums.length != 0. Under this conditoion, the input array need to be analysed as following step. Under the second condition, the input array is actually sepearted to 2 parts, the minimum element is at position k. Then the 2 parts is 0 - (k - 1) and k to (n - 1), both in ascending order and satifies equation nums[0] > nums[nums.length] and nums[i] > nums[j] where i belongs to 0 to k - 1 and j belongs to k to n - 1. Thus the algorithm can be described as following. If the array is not rotated or has a length of 1, the first element is the minimum. Otherwise, do following steps.Set start = 0, end = nums.length - 1. Use binary search. mid = start + (end - start) / 2. If mid is located on the left part of the graph, indicating by nums[mid] > nums[start], set start = mid.If mid is located on the right part of the graph, indicating by nums[mid] < nums[end], set end = mid.if nums[mid] < nums[mid - 1], then nums[mid] is the minimum. The stop condition of the binary search is start < end - 1 since we are using left skewing binary search (i.e. (start + end) / 2 is always floored to left side). Once the start reaches the rightmost position of left part and end reaches the leftmost position of the right part, nums[end] or nums[start + 1] is the minimum. Thus the loop should be terminated. O(1) space and O(logn) time. n is the length of the input array.
The algorithm implementation using java is showed as following.
public class Solution { public int findMin(int[] nums) { if (nums == null || nums.length == 0) return 0; int start = 0; int end = nums.length - 1; if (nums[start] <= nums[end]) { //the array is not rotated, the first element is the smallest return nums[start]; } while (start < end - 1) { int mid = start + (end - start) / 2; if (mid > 0 && nums[mid] < nums[mid - 1]) { return nums[mid]; } if (nums[mid] >= nums[start]) { start = mid; } if (nums[mid] <= nums[end]) { end = mid; } } return nums[start + 1]; }}新聞熱點
疑難解答
