Java旋转数组中的最小数字（图文详解版）

布满荆棘的人生 2023-10-14 17:51 7阅读 0赞

**目录**

1.题目描述

2.题解

分析

具体实现

方法一（遍历）：

方法二（排序）：

方法三（二分查找）：

--------------------

## 1.题目描述 ##

有一个长度为 n 的非降序数组，比如\[1,2,3,4,5\]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了\[3,4,5,1,2\]，或者\[4,5,1,2,3\]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

**示例**

> 输入：\[3, 4, 5, 1, 2\]
> 
> 返回值：1

## 2.题解 ##

### 分析 ###

题目中的数组为

![b5f9b8f525234317a701ff8cce70b96b.png][]

题目要求我们找出其中的最小值

### 具体实现 ###

#### 方法一（遍历）： ####

寻找数组中的最小值，遍历数组即可找到最小值

public class Solution {
        public int minNumberInRotateArray(int[] nums) {
            if(nums.length == 0){
                return -1;
            }
            int min = nums[0];
            for (int i = 1; i < nums.length; i++) {
                if (min > nums[i]) {
                    min = nums[i];
                }
            }
            return min;
        }
    }

#### 方法二（排序）： ####

使用Arrays.sort方法对数组进行降序排序，则nums\[0\]即为数组的最小值

import java.util.Arrays;
    
    public class Solution {
        public int minNumberInRotateArray (int[] nums) {
            if(nums.length == 0){
                return -1;
            }
            Arrays.sort(nums);
            return nums[0];
        }
    }

#### 方法三（二分查找）： ####

数组原本是一个升序数组，旋转之后，数组被分成两部分，前、后半部分分别为升序，后半部分小于前半部分，我们可以利用二分查找的思想，找到其旋转点，即可找到数组的最小值

首先找到数组首尾两端元素，并求出数组中间的下标

![ef90ab01fa11427d83e9a4c04007f798.png][]

再将数组中间值与数组首尾两端元素进行比较，

若**nums\[mid\] > nums\[right\]**，则**left = mid + 1**

![eb7add5297ec40fa94bd3e2124d45f38.png][]

若**nums\[mid\] < nums\[right\]**，则**right = mid**

![1f22f78dbd84491eb7f2858054f58ea3.png][]

若**nums\[mid\] = nums\[right\]**， 则将right向左移动一位，即**right--**

![38f76fb7138a41468f928280eebf8c2a.png][]

然后进入下一次循环，循环的条件为**left < right**

**通过不断缩小范围，最终能够找到数组的最小值**

**![2512850ada2d425db1108dafeb2ca822.png][]**

完整代码

public class Solution {
        public int minNumberInRotateArray(int[] nums) {
            if(nums.length == 0){
                return -1;
            }
            int left = 0;
            int right = nums.length - 1;
            while(left < right){
                //找到数组的中点
                int mid = (left + right) / 2;
                if(nums[mid] > nums[right]){
                    //旋转点在[mid+1, j]中，跳过mid+1左边元素
                    left = mid + 1;
                } else if(nums[mid] < nums[right]){
                    //旋转点在[left, mid]中，跳过mid右边元素
                    right = mid;
                }else{
                    //缩小right继续查找
                    right--;
                }
            }
            //返回旋转点
            return nums[left];
        }
    }

**注**：题目出自牛客网，链接如下

[旋转数组的最小数字\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com]

[b5f9b8f525234317a701ff8cce70b96b.png]: https://img-blog.csdnimg.cn/b5f9b8f525234317a701ff8cce70b96b.png
[ef90ab01fa11427d83e9a4c04007f798.png]: https://img-blog.csdnimg.cn/ef90ab01fa11427d83e9a4c04007f798.png
[eb7add5297ec40fa94bd3e2124d45f38.png]: https://img-blog.csdnimg.cn/eb7add5297ec40fa94bd3e2124d45f38.png
[1f22f78dbd84491eb7f2858054f58ea3.png]: https://img-blog.csdnimg.cn/1f22f78dbd84491eb7f2858054f58ea3.png
[38f76fb7138a41468f928280eebf8c2a.png]: https://img-blog.csdnimg.cn/38f76fb7138a41468f928280eebf8c2a.png
[2512850ada2d425db1108dafeb2ca822.png]: https://img-blog.csdnimg.cn/2512850ada2d425db1108dafeb2ca822.png
[_nowcoder.com]: https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=23269&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking