《劍指offer》面試題7：旋轉陣列的最小數字-有解無憂

題目描述

把一個陣列最開始的若干個元素搬到陣列的末尾，我們稱之為陣列的旋轉，
輸入一個非遞減排序的陣列的一個旋轉，輸出旋轉陣列的最小元素，
例如陣列{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該陣列的最小值為1，
NOTE：給出的所有元素都大于0，若陣列大小為0，請回傳0，

解題思路：

1.如果使用暴力查找法，則可以迅速求解，但是使用這種方法絕對不可能通過面試，達不到面試官考察的要求，求解的方法如下：

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here

        #也可以直接使用暴力求解法得解,雖然暴力求解法，也就是打擂臺演算法也可，但是
        #其所需要計算的時間太多，沒有考慮到我們的時間復雜度的問題

        if len(rotateArray)==0:
            return 0
        min=rotateArray[0]
        for i in rotateArray:
            if i<min:
                min=i
        return min

2.使用二分查找法求解，二分查找法的精髓并不是查找一個有序數列當中的某一個數值，而是通過把一個陣列進行二分后，再進行查找的思想，因此我們將其修改為：

假設有一個陣列：【3，4，5，1，2，3】

left是陣列當中進行比較陣列的最左邊一個數字

right是陣列當中進行比較陣列當中最右邊的一個數字

如果Mid小于了前面的數字，（1<5）那么我們找到了最小數字
我們的目的就是找到一個數字比前面的數字更小
后面的操作相當于不斷改變查找陣列長度的程序
如果mid小于了最后的數字，那么right=mid-1
如果mid大于了最后的數字，那么left=mid+1

這樣不斷地進行移位操作，也就是不斷變化陣列當中的left和right，最終就可以夾逼得到mid的數值小于了前面的數字，這樣這個mid一定使我們所尋找到的最小的數字，

代碼如下：

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray)==0:
            return 0
        left=0
        right=len(rotateArray)-1#-1這個操作非常玄乎....
        while left<=right:
            mid=(left+right)//2
            if rotateArray[mid]<rotateArray[mid-1]:
                return rotateArray[mid]
            elif rotateArray[mid]<rotateArray[right]:
                right=mid-1
            elif rotateArray[mid]>rotateArray[right]:
                left=mid+1

得解也！

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/5292.html

標籤：其他

上一篇：0171. Excel Sheet Column Number (E)

下一篇：嵌入式C-經典筆試題