【剑指offer】面试题八:旋转数组的最小数字
题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为 1.
解法一:
这道题最直观的解法就是遍历一遍数组,这样我们就能找到最小的元素。这种思路的时间复杂度显然是 O(n)。
代码如下:
1 // findMin.c 2 #include "stdio.h" 3 #include "stdlib.h" 4 5 #define N 5 6 7 int findMin(int *arr, int len) 8 { 9 int minVal = arr[0], i; 10 11 for(i = 1; i < len; i++) 12 { 13 if(minVal > arr[i]) 14 minVal = arr[i]; 15 } 16 return minVal; 17 } 18 19 int main(int argc, char *argv[]) 20 { 21 int arr[N] = {3,4,5,1,2}; 22 23 int minNum = findMin(arr, N); 24 printf("The min Num is: %3d",minNum); 25 26 return 0; 27 }
但是这个思路没有利用输入的旋转数组的特性,那么有没有效率更好地办法呢?
解法二:
1、旋转时候的数组实际上可以划分为两个排序的子数组,而前面的子数组的元素都大于或者等于后面子数组的元素。
2、最小的元素刚好是这两个子数组的分界线。
3、第一个元素值应该是大于或者等于最后一个元素的。
在已经有序的数组中我们可以用二分查找法实现 O(log n)的查找,而旋转数组在一定程度上是排序的,因此我们可以试着用二分查找法的思路来寻找这个最小的元素。
分析:
1、我们用两个指针pHead,pTail分别指向数组的第一个元素和最后一个元素,根据二分查找的规则,我们可以找到指向数组中间的元素的指针pMid。
2、如果中间元素*pMid位于前面的递增子数组,那么它应该大于或者等于第一个指针pHead指向的元素。此时数组中最小的元素应该位于*pMid的后面。这样我们可以把第一个指针pHead指向*pMid。这样就可以缩小寻找的范围。移动之后的pHead仍然位于前面的递增子数组中。
3、如果中间元素*pMid位于后面的递增子数组,那么它应该小于或者等于最后一个指针pTail指向的元素。此时数组中最小的元素应该位于*pMid的前面。这样我们就可以把最后一个指针pTail指向*pMid。而移动之后的pTail仍然位于后面的递增子数组中。
4、不管是移动 pHead 和 pTail,查找的范围都会缩小到原来的一半。接下来我们再用更新之后的两个指针,重复做新一轮的查询。
按照上述思路,第一个指针总是指向前面的递增数组的元素,而第二个指针总是指向后面递增数组的元素。最终第一个指针将指向前面子数组的最后一个元素,而第二个指针会指向后面子数组的第一个元素。也就是说,第一个指针与第二个指针最终会指向两个相邻的元素。这就是循环结束的条件。
可以以数组{3,4,5,1,2}为例,画图试着分析。
基于这个思路,我们写出如下的代码:
1 // findMin.cpp 2 #include "stdio.h" 3 #include "stdlib.h" 4 #include <stdexcept> 5 6 #define N 5 7 8 int findMin(int *arr, int len) 9 { 10 if(arr == NULL || len <= 0) 11 throw std::out_of_range("Invalid parameters"); 12 13 int pHead = 0; 14 int pTail = len - 1; 15 16 while(pHead < pTail) 17 { 18 if(pTail - pHead == 1) 19 break; 20 21 int mid = (pHead + pTail) / 2; 22 if(arr[mid] >= arr[pHead]) // 前半部分 23 pHead = mid; 24 else if(arr[mid] <= arr[pTail]) 25 pTail = mid; 26 } 27 28 return arr[pTail]; 29 } 30 31 int main(int argc, char const *argv[]) 32 { 33 int arr[N] = {3, 4, 5, 1, 2}; 34 35 int minVal = findMin(arr, N); 36 printf("The min num is: %d ", minVal); 37 38 return 0; 39 }