題目

　　定義局部最小的概念。arr長度為1時，arr[0]是局部最小。arr的長度為N(N>1)時，如果arr[0] < arr[1]，那么arr[0]是局部最小；如果arr[N-1] < arr[N-2]，那么arr[N-1]是局部最小；如果 0 < i < N-1，既有 arr[i] < arr[i-1]，又有arr[i] < arr[i+1]，那么arr[i]是局部最小。?
　　給定無序數(shù)組arr，已知arr中任意兩個相鄰的數(shù)都不相等。寫一個函數(shù)，只返回arr中任意一個局部最小出現(xiàn)的位置即可。

基本思路

　　本題可以使用二分查找做到時間復雜度O(logN)，空間復雜度O(1)，具體步驟如下：

如果arr長度為1或者，arr[0] < arr[1]，返回0；如果arr[N-1] < arr[N-2]，返回N-1

如果arr長度大于2且arr的左右兩頭都不是局部最小，令left = 1，right = N-2，然后開始二分查找：

（1）令 mid = (left + right) // 2

（2）如果arr[mid] > arr[mid-1]，可知在arr[left…mid-1]上肯定存在局部最小值，令right = mid - 1

（3）如果arr[mid] > arr[mid+1]，可知在arr[mid+1…right]上肯定存在局部最小值，令left = mid + 1

（4）如果不滿足（2）和（3），則mid本身就是局部最小，返回mid即可

（5）重復二分查找步驟，直到left > right
?

def lessMinLocal(L):if L == None or len(L) == 0:return -1if len(L) == 1 or L[0] < L[1]:return 0if L[len(L)-1] < L[len(L)-2]:return 1left = 1right = len(L)-2mid = 0while left < right:mid = (left + right)/2if L[mid] > L[mid-1]:right = mid - 1elif L[mid] > L[mid+1]:left = mid + 1else:return midreturn left

?

總結

以上是生活随笔為你收集整理的在数组中找到一个局部最小的位置的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。