把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個遞增排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。 （如果數(shù)組里有重復(fù)元素，怎么辦？）
答 案： 2分查找的擴充，考慮 [from,to]這段區(qū)間，mid = (from + to) / 2，如果a[mid] < a[to] 則最小值在前半段里，如果a[mid] > a[to], 這段區(qū)間發(fā)生了跳變，所以最小值在后半段區(qū)間里。相等時，當(dāng)然我們可以比較a[mid]和a[from]，但再相等就沒辦法了。偷懶的做法是直接從前后半 段分別找，然后返回最小的，因此最差時間復(fù)雜度是O(n)。當(dāng)存在相等的數(shù)時，可能達到最差時間復(fù)雜度。

#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;
}

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。