vs做网站需要的插件,wordpress设置用户头像,洛阳网络推广公司,提供龙岗网站建设154.已知一个长度为 n 的数组#xff0c;预先按照升序排列#xff0c;经由 1 到 n 次 旋转 后#xff0c;得到输入数组。例如#xff0c;原数组 nums [0,1,4,4,5,6,7] 在变化后可能得到#xff1a; 若旋转 4 次#xff0c;则可以得到 [4,5,6,7,0,1,4] 若旋转 7 次#… 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 暴力解法就不过多赘述了从头到尾遍历一遍看哪个值突然不是保持升序的那他就是最小值或者直接对数组排序然后取首个元素没意义。他人解法首先经过旋转后以最小值 x 为分界点会分为左右两个升序数组并且 x 一定在右数组且为起点因为旋转就是把最小值转到右边去了旋转 0 次可以视为只有右数组。从左右两端 leftright 为区间进行查找中点值 mid 的可能性有三种 mid right: 说明 mid 在右数组所以 mid 可能为 x所以直接排除区间 (mid,right]即 right 更新为 midmid right: 说明 mid 在左数组在左数组 mid 就不可能为 x 了所以所以直接排除区间 [left,mid]即 更新 left 为 mid1mid 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 仍然在 [leftright-1]其次就算 right 对应的就是 x首先 mid left 因为 midrightxx 已经是最小值了那最小值肯定小于等于 left 了同时 leftmidright 是恒成立的因为 mid 是 (leftright)/2但是你这时候 midrightx也就是说 leftmidxmid x 代表了 mid 在左数组因为 x 是右数组起点既然 mid 在左数组那么根据左数组的升序特性 leftmid 恒成立。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(ij){int mid (i j)/2;if(nums[mid] nums[j])imid1;else if(nums[mid] nums[j])jmid;else j--;}return nums[i];}