2

我们得到了一个 API——

removeAndAppend(val)
//Removes val and appends it to the given collection

我们需要使用这个 API 对集合进行排序..

我知道我可以通过 -

for i <- N to 1
    extract max //in O(n) 
    removeAndAppend.. //Consider this O(1)

这是二次元。。

问题是我能做得比这更好吗..？

编辑：我们可以对集合执行 READ 操作，例如 - compare(val1, val2)

4

4 回答 4

1

您可以使用递归和许多集合，在其第一个元素上拆分参数内集合：小于等于和更大，在两者上递归并合并。合并排序的复杂性，搜索互联网。

于 2013-08-20T14:51:34.140 回答
1

没有额外的数据结构/常量空间限制：

您描述的算法本质上是选择排序。O(n2)

如果您可以访问某种迭代器（如果没有，您将如何访问集合中的元素？），我相信使用自定义合并排序可以做得更好，如下所示：

  • 比较元素 1 和 2。removeAndAppend较小的元素，然后removeAndAppend是剩余的元素。对元素 3 和 4、5 和 6，...以及元素 n-1 和 n 执行相同的操作。

    现在，您将对每个包含 2 个元素的子集合进行排序。

  • 合并索引 (1,2) 和 (3,4)。为此，从头开始有 2 个迭代器。首先将一个增加两次。removeAndAppend然后像往常一样使用该函数进行合并排序。对 (5,6) 和 (7,8)、(9,10) 和 (11,12)、... 和 (n-3,n-2) 和 (n-1,n) 执行相同操作。

    现在您将对每个包含 4 个元素的子集合进行排序。

  • 合并与上述类似的大小 4 的集合，然后合并 8、16、32 等，直到达到集合大小。

整个过程将如下所示：

// setSize is how large sets we're currently merging
for setSize = 1; setSize <= n/2; setSize *= 2
  iterator left = begin
           right = begin
  for pos = 1 to n/(2*setSize)
    // here right and left are both at the beginning
    // even after the previous iteration of the loop,
    //   since we've removed and appended all other elements
    // so we only need to increase right by setSize
    right += setSize

    for i = 1 to 2*setSize
      if (left.value <= right.value)
        removeAndAppend(left)
      else
        removeAndAppend(right)

以上只是一个基本的草稿，它可能不是 100% 正确的，并且没有考虑到集合不是 2 的幂（这种情况经常发生）。在这种情况下你需要小心，否则你可能会绕回，或者走得不够远，最终得到一个部分排序的集合。

复杂性分析应该与常规合并排序几乎相同，并导致O(n log n)运行时间。

使用额外的数据结构/没有常量空间限制：

将所有元素提取到另一个集合中，对其进行排序O(n log n)（使用您选择的排序算法）并遍历排序集，removeAndAppend为每个集合调用原始集合。

如果您不允许提取元素，则仍然可以通过使用索引集合来使用此方法，并且要进行比较，只需查找适用的元素即可。但是，为了提高效率，您需要按索引进行恒定时间查找。

于 2013-08-21T08:55:12.657 回答
0

RemoveAndAppend在集合结束时追加？

好吧，如果这种方法O(1)似乎关键问题是如何在集合的未处理部分中找到当前最大值 - 一旦最大值被删除并附加到末尾。

查看从数字数组中获取最小值或最大值的最佳方法是什么？

于 2013-08-21T06:41:33.033 回答
0

阅读整个集合，在您的应用程序中对其进行排序，然后以正确的顺序“removeAndAppend”这些值（现在已知）。

于 2013-08-21T09:06:55.527 回答