在大小爲N的數組的每k個元素中查找最小元素和第二小元素

Question

我試圖在N大小數組的k個元素中找到最小和次要元素（不包括排序和最小/最大堆積）。

使用的第一從0 th元素開始和在第一k元件找到最小和第二小的元件，然後通過1移動開始點並重復該過程的工作原理的傳統方法。但它的複雜性是O(Nk)。如果可能，我需要一個複雜度爲O(N)的解決方案。對此有何建議？

在Jubobs的評論後編輯：例如如果說數組是{12, 1, 78, 90, 57, 89, 56}和k是3，那麼對於第一個k元素(12, 1, 78)最小元素將是1而第二個最小元素將是12。對於第二個k元素(1, 78, 90)，最小元素將是1，第二小元素將是78等等。

以下是代碼片段我與O(Nk)複雜寫着：

int j=0; 
while(j < input.length-k+1) { 
    int i=j; 
    for(i=j; i < j+k; i++) { 
     if(input[i] < min) { 
      min2 = min; 
      min = input[i]; 
     } else if(input[i] > min && input[i] < min2) { 
      min2 = input[i];  
     }     
    } 
} 

Answer 1

您可以使用您一直排序的deque。

在每個步驟中，如果相對於當前步驟中雙側（d.front.index）中的第一個元素早於k步驟，請將其彈出（d.popFront()）。

然後，雖然數組中當前位置的元素小於deque中的最後一個元素（d.back.value），但是可以從deque（d.popBack()）中彈出元素。

最後，將當前值添加到雙端隊列的末尾（d.pushBack()）。

在每一步，d.front.value將是[step - k + 1, step]的最小值。

您可以將該deque存儲爲大小爲k的鏈接列表。然後您可以隨時訪問其中的第二個元素，這將是[step - k + 1, step]中的第二小元素。如果由於彈出每個元素而最終只有一個元素，則必須小心。在這種情況下，彈出的可能是未來查詢的第二小。您可以將它們保存在與deque相似的另一個列表中，請參閱下面的示例。

這是O(n)攤銷，因爲您的數組中的每個元素最多隻能進入和離開雙端隊列。它可能看起來像O(nk)，因爲你會有一些嵌套的循環，但如果你考慮操作的總數，你會發現它實際上是O(n)。

僞跟蹤第二最低

for i = 0, i < n: 
    if not d.empty and i - d.front.index >= k: 
     d.popFront() 
    while not d.empty and d.back.value > a[i]: 
     d.popBack() 

    d.pushBack({index = i, value = a[i]}) 

    output d.front.value as the minimum value in [i - k + 1, i] 

代碼留作練習。

對於示例：

a = {12, 1, 78, 90, 57, 89, 56}, k = 3 

d = {12} 
d = {1} (12 popped, track this) 
d = {1, 78} => we have to output smallest and second smallest in [0, 2]. 
      => smallest is always the first in the deque, so 1 
      => second = min(12 [this was popped], 78) = 12 
d = {1, 78, 90) 
      => smallest 1, second is 78 (12 is too old now) 
d = {57} 
      => 1 popped for being too old, the others for being too large 
      => smallest = 57, second = 78 (last popped) 
d = {57, 89} 
      => smallest = 57, second = 89 
d = {56} 
      => smallest = 56, second = 57 

基本上，你讓一個數組中第二小的。這將包含尚未太舊的彈出的值。這些也將被排序，但下降。

實施例這種方法，其中d2是第二陣列運行：

a = {12, 1, 78, 90, 57, 89, 56} 

d = {12},   d2 = {} 
d = {1},   d2 = {12} 
d = {1, 78},  d2 = {12} 
    => output 1, 12 
d = {1, 78, 90}, d2 = {} - 12 was too old 
    => output 1, 78 
d = {57}   d2 = {90, 78} 
    => output 57, 78 
d = {57, 89}  d2 = {90} - 78 too old 
    => output 57, 89 (if we had 91 instead of 89, we'd have output the 90 in d2) 
d = {56}   d2 = {89, 57} 
    => output 56, 57