Kotlin程序员：轻松找出旋转数组最小元素

【出自YMX面试题】

难度系数：★★★☆☆ 被考察系数：★★★★☆

题目描述：

把一个有序数组最开始的若干个元素搬到数组的末尾，称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3，4，5，1，2}为数组{1，2，3，4，5}的一个旋转，该数组的最小值为1。

分析与解答：

其实这是一个非常基本和常用的数组操作，它的描述如下：

有一个数组X[0…n-1]，现在把它分为两个子数组：x1[0…m]和x2[m+1…n-1]，交换这两个子数组，使数组x由x1x2变成x2x1，例如x={1，2，3，4，5，6，7，8，9}，x1={1，2，3，4，5}，x2={6，7，8，9}，交换后，x={6，7，8，9，1，2，3，4，5}。

对于本题的解决方案，最容易想到的，也是最简单的方法就是直接遍历法。但是这种方法显然没有用到题目中旋转数组的特性，因此，它的效率比较低下。下面介绍一种比较高效的二分查找法。

通过数组的特性可以发现，数组元素首先是递增的，然后突然下降到最小值，然后再递增。虽然如此，但是还有下面三种特殊情况需要注意：

（1）数组本身是没有发生过旋转的，是一个有序的数组，例如序列{1，2，3，4，5，6}。

（2）数组中元素值全部相等，例如序列{1，1，1，1，1，1}。

（3）数组中元素值大部分都相等，例如序列{1，0，1，1，1，1}。

通过旋转数组的定义可知，经过旋转之后的数组实际上可以划分为两个有序的子数组，前面的子数组的元素值都大于或者等于后面子数组的元素值。可以根据数组元素的这个特点，采用二分查找的思想不断缩小查找范围，最终找出问题的解决方案，具体实现思路如下所示：

按照二分查找的思想，给定数组arr，首先定义两个变量low和high，分别表示数组的第一个元素和最后一个元素的下标。按照题目中对旋转规则的定义，第一个元素应该是大于或者等于最后一个元素的（当旋转个数为0，即没有旋转的时候，要单独处理，直接返回数组第一个元素）。接着遍历数组中间的元素arr[mid]，其中mid=（high+low）/2。

（1）如果arr[mid]＜arr[mid-1]，则arr[mid]一定是最小值。

（2）如果arr[mid+1]＜arr[mid]，则arr[mid+1]一定是最小值。

（3）如果arr[high]＞arr[mid]，则最小值一定在数组左半部分。

（4）如果arr[mid]＞arr[low]，则最小值一定在数组右半部分。(www.xing528.com)

（5）如果arr[low]==arr[mid]且arr[high]==arr[mid]，则此时无法区分最小值是在数组的左半部分还是右半部分（例如：{2，2，2，2，1，2}，{2，1，2，2，2，2，2}）。在这种情况下，只能分别在数组的左右两部分找最小值minL与minR，最后求出minL与minR的最小值。

示例代码如下：

程序的运行结果如下：

1

0

算法性能分析：

一般而言，二分查找的时间复杂度为O（log₂^N），对于这道题而言，大部分情况下时间复杂度为O（log₂^N），只有每次都满足上述条件（5）的时候才需要对数组中所有元素都进行遍历，因此，这种方法在最坏的情况下的时间复杂度为O（N）。

引申：如何实现旋转数组功能

分析与解答：

先分别把两个子数组的内容交换，然后把整个数组的内容交换，即可得到问题的解。

以数组x1{1，2，3，4，5}与数组x2{6，7，8，9}为例，交换两个数组后，x1={5，4，3，2，1}，x2={9，8，7，6}，即x={5，4，3，2，1，9，8，7，6}。交换整个数组后，x={6，7，8，9，1，2，3，4，5}

示例代码如下：

程序的运行结果如下：

4 5 1 2 3

算法性能分析：

由于这种方法需要遍历两次数组，因此，它的时间复杂度为O（N）。而交换两个变量的值，只需要使用一个辅助储存空间，所以，它的空间复杂度为O（1）。