以比線性時間更好的方式查找三元組，使得A [n-1]> = A [n] <= A [n + 1]

Question

訪談中給出了一系列數字，例如A[0] >= A[1]和A[N-1] >= A[N-2]。我被要求找到至少一個三聯體，例如A[n-1] >= A[n] <= A[n+1]。

我試着在迭代中解決。採訪者期望比線性時間解決方案更好。我應該如何處理這個問題？

實施例：9 8 5 4 3 2 6 7

答案：3 2 6

Answer 1

線性你可以只通過所述一組迭代，比較它們都做。

你也可以檢查前兩個的斜率，然後做一種二進制斬波/按順序遍歷比較對，直到找到一個相反的斜率。這將分攤到一個好於n時間，我認爲，雖然它不能保證。

編輯：剛剛意識到你的訂購意味着什麼。二進制斬波方法保證在<n時間內完成此操作，因爲保證有一個變化點（假設N-1, N-2是列表的最後兩個元素）。 這意味着你只需要找到它/他們中的一個，在這種情況下，二進制斬將採用分&治又名這麼做是爲了log(n)

Answer 2

我們可以解決這個在O(logn)時間。二進制搜索。好於線性時間。所以我們需要找到一個三元組，例如A[n-1] >= A[n] <= A[n+1]。

首先找到給定數組的中間值。如果mid比左邊小，比右邊大。然後返回，這就是你的答案。順便說一下，這將是遞歸中的基本情況。另外如果len(arr) < 3那麼太回。另一個basecase。

現在出現遞歸場景。何時遞歸，我們需要進一步檢查權利。爲此，如果mid大於其左側的元素，則考慮將數組的左側開始作爲子問題，並使用此新數組進行遞歸。在這一點上有形的方面，即我們必須...2...與指數n被6.因此，我們向左移動，看是否元素的2左側完成了三重。

否則，如果mid在其右側子陣列上大於元素，則考慮數組右側的mid + 1作爲子問題並遞歸。

---

更多理論：以上應足以瞭解這個問題，但閱讀。這個問題實質上歸結爲在一組給定元素中找到局部最小值。如果陣列中的數字小於其左側和右側數字，則數組中的數字稱爲局部最小值，其精確歸結爲A[n-1] >= A[n] <= A[n+1]。

一個給定的數組，使其前2個元素減少，最後2個元素增加HAS具有局部最小值。這是爲什麼？讓我們通過否定來證明這一點。如果前兩個數字減少，並且沒有局部最小值，則意味着第三個數字小於第二個數字。否則第二個數字將是當地最低標準。遵循相同的邏輯第4個數字將不得不小於第3個數字等等等等。所以數組中的數字必須按照降序排列。這違背了最後兩個數字按遞增順序的約束。這通過否定證明需要一個局部最小值。

上述理論認爲一個O(n)線性的做法，但我們肯定可以做的更好。但是這個理論明確地給了我們關於這個問題的不同觀點。

---

代碼：這裏的Python代碼（僅供參考 - 在計算器的文本編輯器寫意被輸入，它可能misbheave）。

def local_minima(arr, start, end): 
    mid = (start+end)/2 

    if mid-2 < 0 and mid+1 >= len(arr): 
     return -1; 

    if arr[mid-2] > arr[mid-1] and arr[mid-1] < arr[mid]: #found it! 
     return mid-1; 

    if arr[mid-1] > arr[mid-2]: 
     return local_minima(arr, start, mid); 
    else: 
     return local_minima(arr, mid, end); 

請注意，我只是返回n的索引。要打印出三元組，只需執行-1和+1即可返回索引。 source

Answer 3

這聽起來像你問的是：

你有數字的序列。它開始下降並繼續下降，直到元素n，然後它開始增加，直到序列結束。找到n。

這是線性的時間（非最佳）的解決方案：

for (i = 1; i < length(A) - 1; i++) 
{ 
    if ((A[i-1] >= A[i]) && (A[i] <= A[i+1])) 
     return i; 
} 

做得比線性時間更好，你需要用你的事實得到了一系列減小後增大的信息。

考慮A[i]和A[i+1]之間的差異。如果A[i] > A[i+1]，那麼n > i，因爲值仍然在下降。如果A[i] <= A[i+1]，那麼n <= i，因爲值現在正在增加。在這種情況下，您需要檢查A[i-1]和A[i]之間的差異。

這是在日誌時間的解決方案：

int boundUpper = length(A) - 1; 
int boundLower = 1; 
int i = (boundUpper + boundLower)/2; //initial estimate 

while (true) 
{ 
    if (A[i] > A[i+1]) 
     boundLower = i + 1; 
    else if (A[i-1] >= A[i]) 
     return i; 
    else 
     boundUpper = i; 

    i = (boundLower + boundUpper)/2; 
} 

我將讓你在必要的錯誤檢查添加的情況下A沒有滿足條件的元素。