今天我們來講一個比較簡單的題目，這是一個好玩的題目，希望大家可以思考一下。

原題：

有一個隊列，這個隊列有n個元素，并且這個隊列單調上升，現在我們進行這麼一個操作，把前面若幹個元素剪切下來，粘到隊列後面。例如（1,2,3,4,5,6,7 我們把前3個進行這個操作，變成4,5,6,7,1,2,3；如果是4個，變成5,6,7,1,2,3,4；如果是0個，原隊列不變）。現在給一個操作後的隊列，求隊列中最小的元素是多少？（用越快的算法越好）

思考：

這個題目，99%的人可以用O(n)的算法來解決。但是，這是最優的麼？

我們來想一想有沒有更優的解法，既然比O(n)更優，那麼有可能是O(logn)。我們朝這個方向思考，我們想起來我們以前學過二分查找。我們來回想一下二分查找的特性。

二分查找又稱折半查找，優點是比較次數少，查找速度快，平均性能好。但使用二分查找必須滿足下面條件，

1. 必須采用順序存儲結構

2.必須按關鍵字大小有序排列。

這個題好像并不滿足是一個有序的隊列，但是至少有可能是兩個有序的隊列。

如果我們随機截取這個中間某一段，那麼有兩種情況。

橙色部分是一個兩段上升序列，而黃色的部分是一段連續上升的序列。

我們再來進一步思考，如果是黃色的情況，最小的一定是出現在最左邊的。如果是橙色的情況，那麼最小的出現在中間的斷層。

再繼續思考，假設這段線段的索引是[l,r],那麼當我們取中間的mid，當我們發現a[l] < mid 的時候，是有可能是下面的情況。

或者

我們用findMin(l, r)來表示這兩種情況。當a[i] < a[mid]的時候，[l,mid]一定是上面黃色的框，[mid 1, r] 可能是黃色的，也可能是橙色的。

findMin(l,r) = min(a[l], find(mid 1, r));

我們來想另外一種情況， a[i] > a[mid],那麼情況如下：

區間[mid,r]一定是上面黃色的框框，而[l, mid-1]則是橙色的框框，最小的可能是a[mid], 或者findMin(l, mid-1)。表達式為

findMin(l,r) = min(a[mid], find(l, mid - 1));

總結:

我們發現這個題目也是可以用二分法來解決的.這是最優的做法，好友說一年面試幾十個人，每次都問這個，隻有兩三個可以短時間内想到結果。

歡迎大家關注我的頭條号，也可以關注我的微信公衆号（ddpcyh）,會提供算法學習資料，一起來學習算法吧。

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部