面试题8:旋转数组的最小数字

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


分析

很自然地,最直观的解法就是设置一个最小值,并顺次检查数组的每一个元素,如果小于最小值,就更新这个值。最后将它输出即可。

最容易想到的往往都不是最优的解法。这种算法的时间复杂度为O(n),没有利用这是一个已排序数组的旋转这个特性。代码从略。

一般我们对一个已排序数组进行查找较好的方法是二分法。所以我们试着用来解这道题。

假设这个数组有n个元素,则它可以分为有旋转和无旋转两种情况(旋转n次也相当于无旋转)。当有旋转时,我们将数组分成左右两部分,他们都是递增的子数组,而最小元素是右子数组的第一个元素,因此可以在两部分里面分别用二分法来查找。而无旋转就相当于有旋转的一个特例(一个子数组为空),所以也可依照此法来解。下面是参考思路:

设数组为arr,其左右元素的下标分别是left和right,我们求得其中间元素的下标mid=left+(right-left)/2;如果arr[mid]>arr[mid],表明mid在左子数组中,此时令left=mid。否则表明mid在右子数组中,令right=mid。继续循环即可。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int Min(vector<int> arr)
{
int left=0,right=arr.size()-1;
int mid;
if(arr[left]<arr[right])
return left;
while(left<right-1)
{
if(right-left==1)
{
mid=right;
break;
}
mid=left+(right-left)/2;
if(arr[mid]==arr[left] && arr[mid]==arr[right])
return arr[mid];
if(arr[mid]<=arr[right])
right=mid;
else if(arr[mid]>=arr[left])
left=mid;
}
return arr[mid];
}

然而,当数组为{1,0,1,1,1}时,使用上述算法是无法找出最小元素的。因为刚开始left=0,right=4,mid=2,此时arr[left]=arr[mid]==arr[right],算法就直接返回1,而数组真正最小的元素是0。所以需要加一个判断条件,如果左中右的值相等时,则需要顺序查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int MinInOrder(vector<int> arr)
{
if(arr.size()<=0)
return -1;
int min=0;
int i;
for(i=0;i<arr.size();++i)
{
if(arr[i]<arr[min])
min=i;
}
return arr[min];
}

然后将

    if(arr[mid]==arr[left] && arr[mid]==arr[right])
            return arr[mid];
1
改为
if(arr[mid]==arr[left] && arr[mid]==arr[right]) return MinInOrder(arr);

即可。

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往