154.已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到:
若旋转 4 次,则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次,则可以得到 [0,1,4,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 = [1,3,5]
输出:1
示例 2:
输入:nums = [2,2,2,0,1]
输出:0文章来源地址https://www.toymoban.com/news/detail-642959.html
- 暴力解法就不过多赘述了,从头到尾遍历一遍看哪个值突然不是保持升序的,那他就是最小值,或者直接对数组排序然后取首个元素,没意义。
- 他人解法:首先经过旋转后以最小值 x 为分界点会分为左右两个升序数组,并且 x 一定在右数组,且为起点,因为旋转就是把最小值转到右边去了(旋转 0 次可以视为只有右数组)。从左右两端 left,right 为区间进行查找,中点值 mid 的可能性有三种:
- mid < right: 说明 mid 在右数组,所以 mid 可能为 x,所以直接排除区间 (mid,right],即 right 更新为 mid
- mid > right: 说明 mid 在左数组,在左数组 mid 就不可能为 x 了,所以所以直接排除区间 [left,mid],即 更新 left 为 mid+1
- mid = right: 此时由于数组元素可能重复比如 [2,2,2,0,2] 和 [2,0,2,2,2],此时无法确定 mid 在左右哪个数组,不能直接去掉一部分区间了。但是无论是哪种情况,right 肯定是没用了,因为就算 right 等于 x,那我 mid 也等于 x,所以就谨慎地只去掉 right,也就是 right = right - 1。
- 当 mid = right 时。换个说法再解释一下:首先如果 x 小于 right 对应的值,那 right 去掉也就去掉了,x 仍然在 [left,right-1];其次就算 right 对应的就是 x,首先
mid <= left
,因为 mid=right=x,x 已经是最小值了,那最小值肯定小于等于 left 了,同时 left<=mid<right 是恒成立的(因为 mid 是(left+right)/2
),但是你这时候 mid=right=x,也就是说 left<=mid<x,mid < x 代表了 mid 在左数组(因为 x 是右数组起点),既然 mid 在左数组,那么根据左数组的升序特性 left<=mid 恒成立。mid <= left 并且 mid >= left
,那就只能说 mid 岂不是就等于 left,由于区间 [left,mid] 是升序的,那么 left - mid 的值都是相等的。在 right 对应 x 时减 1 后代表的其实就是正好把右数组全部抛弃了,剩下的左数组全等,且都等于 x,那么无论你怎么查找,最后剩下的值都等于我们最终要的 x。
- 为什么 mid 不和 left 比较,因为二分的目的是为了判断 mid 处于左右的哪个数组。mid > left 时比如 [1,2,3,4,5] 和 [3,4,5,1,2] mid 分别在右数组和左数组,这就无法判断了。
-
public int minArray(int[] nums) { int i = 0,j = nums.length - 1; while(i<j){ int mid = (i + j)/2; if(nums[mid] > nums[j])i=mid+1; else if(nums[mid] < nums[j])j=mid; else j--; } return nums[i]; }
文章来源:https://www.toymoban.com/news/detail-642959.html
到了这里,关于从零学算法154的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!