网站验收,微网站平台微网站建设方案模板,手机appui设计,太原网站定制已知一个长度为 n 的数组#xff0c;预先按照升序排列#xff0c;经由 1 到 n 次 旋转 后#xff0c;得到输入数组。例如#xff0c;原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到#xff1a;
若旋转 4 次#xff0c;则可以得到 [4,5,6,7,0,1,2]若旋转 7 次#xff0…已知一个长度为 n 的数组预先按照升序排列经由 1 到 n 次 旋转 后得到输入数组。例如原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到
若旋转 4 次则可以得到 [4,5,6,7,0,1,2]若旋转 7 次则可以得到 [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 它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 示例 1
输入nums [3,4,5,1,2]
输出1
解释原数组为 [1,2,3,4,5] 旋转 3 次得到输入数组。示例 2
输入nums [4,5,6,7,0,1,2]
输出0
解释原数组为 [0,1,2,4,5,6,7] 旋转 3 次得到输入数组。示例 3
输入nums [11,13,15,17]
输出11
解释原数组为 [11,13,15,17] 旋转 4 次得到输入数组。提示
n nums.length1 n 5000-5000 nums[i] 5000nums 中的所有整数 互不相同nums 原来是一个升序排序的数组并进行了 1 至 n 次旋转
代码实现
class Solution { public int findMin(int[] nums) { // 初始化low和high指针分别指向数组的第一个和最后一个元素 int low 0; int high nums.length - 1; // 当low指针小于high指针时进行循环 while (low high) { // 找到中间元素的索引 int pivot low (high - low) / 2; // 如果中间元素小于high指向的元素说明最小元素在左半部分或者就是中间元素 if(nums[pivot] nums[high]) { // 更新high指针到中间元素的位置 high pivot; } else { // 如果中间元素不小于high指向的元素说明最小元素在右半部分 // 更新low指针到中间元素的下一个位置 low pivot 1; } } // 循环结束时low和high指针会指向同一个位置这个位置就是最小元素的位置 // 返回这个位置上的元素值 return nums[low]; }
}
