程序员经典面试题：数组旋转算法

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 （如果数组里有重复元素，怎么办？）
答 案： 2分查找的扩充，考虑 [from,to]这段区间，mid = (from + to) / 2，如果a[mid] < a[to] 则最小值在前半段里，如果a[mid] > a[to], 这段区间发生了跳变，所以最小值在后半段区间里。相等时，当然我们可以比较a[mid]和a[from]，但再相等就没办法了。偷懒的做法是直接从前后半 段分别找，然后返回最小的，因此最差时间复杂度是O(n)。当存在相等的数时，可能达到最差时间复杂度。

#include<iostream>
 
using namespace std;
  
int a[1000005];
  
int find(int *a,int from,int to) {
        if (from == to - 1) {
                return (a[from] < a[to])?a[from]:a[to];
        }
        if (from == to) {
                return a[to];
        }
        int mid = (from + to) >> 1,x;
        if (a[mid] < a[to]) {
                x = find(a, from, mid - 1);
                if (x > a[mid]) {
                        x = a[mid];
                }
        }
        else if (a[mid] > a[to]) {
                x = find(a,mid + 1, to);
        }
        else {
                int  x1 = find(a, from, mid - 1);
                int  x2 = find(a, mid + 1, to );
                x = (x1 < x2)?x1:x2;
                if (x > a[mid]) {
                        x = a[mid];
                }
        }
        return x;
}
  
  
int main() {
int i,n;
        while (scanf("%d",&n) != EOF) {
                for (i = 0; i < n; ++i) {
                        scanf("%d", a + i);
                }
                printf("%d\n",find(a,0,n -1));
        }
        return 0;
}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。