在大小为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