其中<code>N</code>是陣列A的長度構造的陣列<code>B</code>使得<code>B[i] = min(A[i], A[i+1], ..., A[i+K-1])</code>，其中<code>K</code>將給出與來自現有陣列

鑑於整數A[1...n-1]的陣列構造的陣列。陣列B將具有N-K + 1個元素。其中<code>N</code>是陣列A的長度構造的陣列<code>B</code>使得<code>B[i] = min(A[i], A[i+1], ..., A[i+K-1])</code>，其中<code>K</code>將給出與來自現有陣列

我們可以使用min-heap解決問題爲k個元素構造min-heap-O（k）。對於每個下一個元素，刪除第一個元素並插入新元素和堆積。

因此最壞情況時間 - O（（N-K + 1）* K）+ O（k）的空間 - O（K）

我們能否做得更好？

來源

2012-06-22 Luv

也許這將有助於：http://stackoverflow.com/a/11044634/1400768 – nhahtdh

如果在OP算法中我們可以做得更好，我們可以將昂貴的「heapify」過程更改爲更便宜的「upheap」或「downheap」。這給出了O（n * log（k））的時間複雜度。或者，如果我們遍歷輸入數組並將每個元素放到大小爲'k'的最小隊列中，我們可以在O（n）時間內完成。 Min-queue是一個可以在O（1）時間內執行find-min的隊列。它可以作爲一對最小堆棧來實現。詳情請參閱this answer。

來源

2012-06-22 15:49:01

但是在刪除時我們必須搜索元素，因此在這裏將是O（k）not log（k）。這就是爲什麼我說最壞的情況複雜度是O（（n-k + 1）* k）+ O（k） – Luv

@Luv：如果我們跟蹤每個堆元素的位置，就不需要搜索被刪除的元素。 –

其中<code>N</code>是陣列A的長度構造的陣列<code>B</code>使得<code>B[i] = min(A[i], A[i+1], ..., A[i+K-1])</code>，其中<code>K</code>將給出與來自現有陣列

回答

相關問題