【LeetCode】寻找旋转排序数组中的最小值 Java 题解

2021 年 12 月 15 日
本文字数：875 字
阅读完需：约 3 分钟

题目描述

已知一个长度为 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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

示例 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] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]输出：11解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法每日一题是寻找旋转排序数组中的最小值。这个题目可以用二分算法求解。题目指出了排序数组,说明数组是有序的。我们首先假设固定旋转数组后的最后一个位置，然后每一个数组元素 nums[i] 与 nums[n - 1] 比较，会有大于，或者小于等于两种情况。就可以转换成一个新的有序数组，这就和我们平时常见的排序数组一样，使用二分求解。具体实现代码如下：

通过代码

class Solution {    public int findMin(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;            }        }        return nums[right];    }}