排序與選擇一個幾乎排序後的數組

給定長度Ñ的陣列，其中每個項目具有從它的最終位置的排序後的數組中至多的log（n）的距離，如何有效地完成我排序，並我如何找到價值物品（select-k）的第k個？排序與選擇一個幾乎排序後的數組

這是我開始的想法：

對於排序，使用比較模式，我可以得到有將約爲O（（LOGN）^ n）的可能的排列，因此的最大深度比較樹應該是O（nloglogn）。另外，對於選擇的問題，我有一種直覺，如果我看LOGN的範圍爲k個項的每一側（2logn - 1），我可以在使用確定性選擇算法O（logn），但我不確定如何證明此方法的正確性。

請注意，我是而不是正在尋找代碼（使用任何語言），但抽象算法的草圖和時間複雜度。

謝謝。

來源

2017-07-28 Mickey

如果你不看對於代碼，最好轉到https://cs.stackexchange.com/。 – hgazibara

使用minHeap長度

x=log(n)

開始從開始的，推動要素堆和X插入後相應，你會發現最小的元素，並繼續等掃描其他元素。

複雜性 -

O(n(log(x))) = x*log(x)(for heap operations for first x elements) + (n-x)(log (x))(for remaining elements) 
x=log(n);

你可以用自己的方式來識別通過跟蹤有多少個元素已經排序排序第k個值......

來源

2017-07-28 08:42:06

與minHeap的好主意。對於第k個值 - 我想要得到更好的複雜度，因此它應該是一個不同的算法（與排序分離），你有什麼想法嗎？ – Mickey

好吧，你只需要找到第k個最小的元素，然後？ –

是的，（和排序，但你已經回答:) :) – Mickey

排序與選擇一個幾乎排序後的數組

回答

相關問題