一道腾讯算法题，拿好不谢~

痛定思痛。 2023-02-20 02:37 28阅读 0赞

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 **面试题11.旋转数组的最小数字**。在腾讯的算法面试环节出现频率较高，属于简单难度。

题目链接：[https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof][https_leetcode-cn.com_problems_xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof]

**一、题目描述**

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组`[3,4,5,1,2]` 为 `[1,2,3,4,5]` 的一个旋转，该数组的最小值为 1。

**示例 1：**

输入：[3,4,5,1,2]
    输出：1

**示例 2：**

输入：[2,2,2,0,1]
    输出：0

## **二、题目解析** ##

这道题最直观的解法是 **从头到尾遍历数组一次**，轻轻松松就能找出最小的元素。

这种思路的时间复杂度显然是 **O(n)**。

很显然，这种做法 **没有利用输入的旋转数组的特性，所以在面试环节面试官肯定会问你：还能优化一下吗？**。

一般的，O(n) 复杂度的优化我们都是往 **二分查找** 这个思路上去考虑的。

设置 `start`, `end` 指针分别指向 `numbers` 数组左右两端，取它们的中点 mid = (start + end ) / 2，然后将 **numbers\[mid\]** 与 **numbers\[end\]** 进行对比：

### **1、当 numbers\[mid\] > numbers\[end\]** ###

此时，mid 在 **左排序数组** 中，而旋转点 x 一定在 \[ mid + 1，end \] 闭区间内，所以接下来的操作是在 \[ mid + 1，end \] 区间内寻找旋转点，相应的，改变 start 的值为 mid + 1。

![v2-0f862d67bc3dafd0f9bbcbaf79291d0b\_b.jpg][v2-0f862d67bc3dafd0f9bbcbaf79291d0b_b.jpg]

### **2、numbers\[mid\] < numbers\[end\]** ###

此时，mid 在 **右排序数组** 中，而旋转点 x 一定在 \[ start，mid \] 闭区间内，所以接下来的操作是在 \[ start，mid \] 区间内寻找旋转点，相应的，改变 end 的值为 mid 。

![v2-00758f01af11c787c7ccc5d35eea294c\_b.jpg][v2-00758f01af11c787c7ccc5d35eea294c_b.jpg]

### **3、numbers\[mid\] = numbers\[end\]** ###

![v2-ca219c5f16c6c1908da7805388156196\_b.jpg][v2-ca219c5f16c6c1908da7805388156196_b.jpg]

## **三、动画描述** ##

[知乎视频][Link 1]

## **四、图片描述** ##

![v2-89736b630fbaa6eefe9cefd0d15c962b\_b.jpg][v2-89736b630fbaa6eefe9cefd0d15c962b_b.jpg]

![v2-6ac1d8bd86ffb67980fe77dfa0f2cb5c\_b.jpg][v2-6ac1d8bd86ffb67980fe77dfa0f2cb5c_b.jpg]

![v2-25db13e89ac0ce379e7545f4eb8171a9\_b.jpg][v2-25db13e89ac0ce379e7545f4eb8171a9_b.jpg]

![v2-8ef481de97b7ff3b953c2b0f14a48330\_b.jpg][v2-8ef481de97b7ff3b953c2b0f14a48330_b.jpg]

![v2-2aaa492e96186f4c13e8789e40624f5a\_b.jpg][v2-2aaa492e96186f4c13e8789e40624f5a_b.jpg]

![v2-3afca4bfac2ad1808fa7810e2c25b5c1\_b.jpg][v2-3afca4bfac2ad1808fa7810e2c25b5c1_b.jpg]

![v2-c8b5b6926ab70b91639cee0d34b2fd1e\_b.jpg][v2-c8b5b6926ab70b91639cee0d34b2fd1e_b.jpg]

![v2-7acd2fe0c5fcb0ddefd50549c7717509\_b.jpg][v2-7acd2fe0c5fcb0ddefd50549c7717509_b.jpg]

![v2-4ee9daaa2fe4d0990e33fb8e4e0075b2\_b.jpg][v2-4ee9daaa2fe4d0990e33fb8e4e0075b2_b.jpg]

![v2-456a6dabf496666431f710acdf01b36c\_b.jpg][v2-456a6dabf496666431f710acdf01b36c_b.jpg]

![v2-da81c3460ec4876c147065eec5b9b342\_b.jpg][v2-da81c3460ec4876c147065eec5b9b342_b.jpg]

![v2-2cf892e194599d7dde345ab887ec359d\_b.jpg][v2-2cf892e194599d7dde345ab887ec359d_b.jpg]

![v2-9ea9f2ba67bdb05f636f3ad34e4ece86\_b.jpg][v2-9ea9f2ba67bdb05f636f3ad34e4ece86_b.jpg]

![v2-7f9fe660953255a9405a237f39c4628f\_b.jpg][v2-7f9fe660953255a9405a237f39c4628f_b.jpg]

![v2-0255ea8060d96fac9ab761d79f846a3a\_b.jpg][v2-0255ea8060d96fac9ab761d79f846a3a_b.jpg]

![v2-cb9cbef772655eeaad5ecd9a469b6645\_b.jpg][v2-cb9cbef772655eeaad5ecd9a469b6645_b.jpg]

![v2-070d7048449975f2cc40a6f038d47d54\_b.jpg][v2-070d7048449975f2cc40a6f038d47d54_b.jpg]

![v2-6577e1da3d3b45a963f5baf1cae6d8d6\_b.jpg][v2-6577e1da3d3b45a963f5baf1cae6d8d6_b.jpg]

## **五、参考代码** ##

class Solution {
        public int minArray(int[] numbers) {
            //设置 start, end 指针分别指向 numbers 数组左右两端
            int start = 0, end = numbers.length - 1;
    
            //循环判断处理，直到找到结果
            while (start < end) {
    
                // mid 为中点（这里向下取整，比如 （ 2 + 7 ）/ 2 = 4 )
                int mid = (start + end) / 2;
    
                //当 mid 点所在元素大于数组末端的元素时，这意味着 [start , mid] 是有序的数组
                if (numbers[mid] > numbers[end]){
    
                    // 所以旋转点在 [ mid + 1, end ] 区间里面 ，更新 start 的位置为 mid + 1
                    start = mid + 1;
    
                }else if (numbers[mid] < numbers[end]){
    
                    // 当 mid 点所在元素小于数组开始端的元素时，这意味着 [mid , end] 是有序的数组
                    // 所以旋转点在 [ start, mid ] 区间里面 ，更新 end 的位置为 mid 
                    end = mid;
    
                    //思考题 ：为什么 start 是更新为 mid + 1，而 end 却是更新为 mid
    
                }else{
    
                    //此时，出现了 numbers[mid] = numbers[end] 的情况，无法判断 
                    //    [ start , mid ]  为有序数组区间
                    //  还是  [ mid , end ]  为有序数组区间
                    //  比如： [1, 0, 1, 1, 1] 和  [1, 1, 1, 0, 1]
                    //  所以这里采取遍历的方式
                    return findMin(numbers,start,end);
    
                }
            }
            return numbers[start];
        }
    
    
         public int findMin(int[] numbers,int start,int end){
    
            int result = numbers[start];
    
            for(int i = start;i <= end;i++){
    
                if (numbers[i] < result) {
                    result = numbers[i];
                }
            }
            return result;
        }
    }

## **六、复杂度分析** ##

### **时间复杂度** ###

时间复杂度为 O(log2N)。

### **空间复杂度** ###

空间复杂度为 O(1)。

## **七、相关标签** ##

*  二分查找
 *  数组

[https_leetcode-cn.com_problems_xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof]: https://link.zhihu.com/?target=https%3A//leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
[v2-0f862d67bc3dafd0f9bbcbaf79291d0b_b.jpg]: https://img-blog.csdnimg.cn/img_convert/83ff94fdc293bf4dce9747eb4c6516d1.png
[v2-00758f01af11c787c7ccc5d35eea294c_b.jpg]: https://img-blog.csdnimg.cn/img_convert/5da5eb45fa25d71f39ef47edafea8a67.png
[v2-ca219c5f16c6c1908da7805388156196_b.jpg]: https://img-blog.csdnimg.cn/img_convert/430083d725207ae64067e3641926f895.png
[Link 1]: https://www.zhihu.com/zvideo/1258353600083988480
[v2-89736b630fbaa6eefe9cefd0d15c962b_b.jpg]: https://img-blog.csdnimg.cn/img_convert/1680ba7660016e1d2d7889527db90c5b.png
[v2-6ac1d8bd86ffb67980fe77dfa0f2cb5c_b.jpg]: https://img-blog.csdnimg.cn/img_convert/0ed58cdba428c673f657124007bf0d3b.png
[v2-25db13e89ac0ce379e7545f4eb8171a9_b.jpg]: https://img-blog.csdnimg.cn/img_convert/f1d35be2ad8e8df161d01e9feeaa65da.png
[v2-8ef481de97b7ff3b953c2b0f14a48330_b.jpg]: https://img-blog.csdnimg.cn/img_convert/10e428996f982439b580e59ffb8ae0b1.png
[v2-2aaa492e96186f4c13e8789e40624f5a_b.jpg]: https://img-blog.csdnimg.cn/img_convert/8ef8773b6ffec7ed2825ee649aeb7235.png
[v2-3afca4bfac2ad1808fa7810e2c25b5c1_b.jpg]: https://img-blog.csdnimg.cn/img_convert/4f13978deb5a8b41acad37408967b043.png
[v2-c8b5b6926ab70b91639cee0d34b2fd1e_b.jpg]: https://img-blog.csdnimg.cn/img_convert/aceffee7ee23f0caf299aae1ef52285f.png
[v2-7acd2fe0c5fcb0ddefd50549c7717509_b.jpg]: https://img-blog.csdnimg.cn/img_convert/2b231f12f7c1c346c1074f0b4a20d5d8.png
[v2-4ee9daaa2fe4d0990e33fb8e4e0075b2_b.jpg]: https://img-blog.csdnimg.cn/img_convert/d0a11f290476edb5f386be702d9ebdbc.png
[v2-456a6dabf496666431f710acdf01b36c_b.jpg]: https://img-blog.csdnimg.cn/img_convert/64f9f9a2f93e40364e2aa4e416f57005.png
[v2-da81c3460ec4876c147065eec5b9b342_b.jpg]: https://img-blog.csdnimg.cn/img_convert/12b9e293c26613b2cd202612aef6d2f9.png
[v2-2cf892e194599d7dde345ab887ec359d_b.jpg]: https://img-blog.csdnimg.cn/img_convert/19e784a9707f56cbd507a198c7f0e7ba.png
[v2-9ea9f2ba67bdb05f636f3ad34e4ece86_b.jpg]: https://img-blog.csdnimg.cn/img_convert/b363a45b2f495c4f08bd7dcc17bc719c.png
[v2-7f9fe660953255a9405a237f39c4628f_b.jpg]: https://img-blog.csdnimg.cn/img_convert/a9266247d4df5a54d7a54e539caed886.png
[v2-0255ea8060d96fac9ab761d79f846a3a_b.jpg]: https://img-blog.csdnimg.cn/img_convert/32bf165045a75a0647d161aa8b7cc04c.png
[v2-cb9cbef772655eeaad5ecd9a469b6645_b.jpg]: https://img-blog.csdnimg.cn/img_convert/f3d95b435481f6cd49f52ba5657523ca.png
[v2-070d7048449975f2cc40a6f038d47d54_b.jpg]: https://img-blog.csdnimg.cn/img_convert/16be27d2dbbe72f9bb2931a9c2c47e98.png
[v2-6577e1da3d3b45a963f5baf1cae6d8d6_b.jpg]: https://img-blog.csdnimg.cn/img_convert/187846ccbb219f6230dd7a54b7f80b9d.png