题目描述
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]若旋转 4 次，则可以得到 [0,1,2,4,5,6,7]注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
代码
public class DayCode { public static void main(String[] args) { int[] nums = new int[]{3, 4, 5, 1, 2}; int ans = new DayCode().findMin(nums); int ans1 = new DayCode().findMin1(nums); System.out.println("ans is " + ans); System.out.println("ans is " + ans1); }
/** * 时间复杂度 O(n) * 空间复杂度 O(1) * * @param nums * @return */ public int findMin(int[] nums) { int ans = Integer.MAX_VALUE; for (int num : nums) { ans = Math.min(num, ans); } return ans; }
/** * 时间复杂度 O(log n) * 空间复杂度 O(1) * * @param nums * @return */ public int findMin1(int[] nums) { int n = nums.length; int left = 0; int right = n - 1; while (left < right) { int mid = left + (right - left) / 2;
if (nums[mid] < nums[right]) { right = mid; } else { left = mid + 1; } }
int ans = nums[left]; return ans; }}
复制代码
总结
/** * Searches the specified array of longs for the specified value using the * binary search algorithm. The array must be sorted (as * by the {@link #sort(long[])} method) prior to making this call. If it * is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched * @param key the value to be searched for * @return index of the search key, if it is contained in the array; * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The * <i>insertion point</i> is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or <tt>a.length</tt> if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. */ public static int binarySearch(long[] a, long key) { return binarySearch0(a, 0, a.length, key); } // Like public version, but without range checks. private static int binarySearch0(long[] a, int fromIndex, int toIndex, long key) { int low = fromIndex; int high = toIndex - 1;
while (low <= high) { int mid = (low + high) >>> 1; long midVal = a[mid];
if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. }
复制代码
评论