1

structs我有一个被调用的数组struct Test testArray[25]。

Test struct包含一个名为 的成员int size。

根据成员，获取另一个数组的最快方法是什么，该数组Test structs包含原始数组中的所有内容，不包括最大的 5 个size？不修改原始数组。

注意：数组中的项目数量可能要大得多，只是将其用于测试，并且值可能是动态的。只是想要一个较慢的子集进行测试。

我正在考虑制作原始副本，testArray然后对该数组进行排序。Test structs然后返回一个不包含前 5 或后 5的数组（取决于 asc 或 desc）。

或者

遍历testArray寻找最大的 5，然后制作原始数组的副本，不包括最大的 5。与已找到的最大 5 的数组相比，这种方式似乎会遍历数组太多次。

跟进问题：

这就是我现在正在做的事情，让我知道你的想法吗？

考虑到我感兴趣的最大元素的数量将保持不变，我正在遍历数组并获取最大元素并将其交换到数组的前面。然后我跳过第一个元素，然后寻找最大的元素，然后将其交换到第二个索引中……依​​此类推。直到我有前 5 个最大的。然后我停止排序，只是将第六个索引复制到一个新数组的末尾。

这样，无论如何，我只遍历数组 5 次。而且我不必对整个事情进行排序。

4

4 回答 4

3

使用线性时间选择算法的部分排序将在 O(n) 时间内完成此操作，其中排序将是 O(nlogn)。

引用部分排序页面：

上述线性时间选择算法可用于在最坏情况线性时间 O(n) 中找到 k 个最小或 k 个最大元素。要找到 k 个最小元素，请使用线性时间中位数选择算法找到第 k 个最小元素。之后，以第 k 个最小元素为基准对数组进行分区。k 个最小的元素将是前 k 个元素。

您可以在 O(n) 中找到 k 个最大的项目，尽管制作数组的副本或指向每个元素的指针数组（更智能）也会花费您一些时间，但无论如何您都必须这样做。

如果您希望我对所涉及的算法给出完整的解释，请发表评论。

更新： 关于您的后续问题，这基本上建议对列表进行五次迭代......这将起作用。但它对列表的迭代次数超出了您的需要。在一次遍历中找到 k 个最大元素（使用 O(n) 选择算法）比这要好得多。这样你迭代一次来创建你的新数组，然后再做一次选择（如果你使用中位数，你不需要第三次迭代来删除五个最大的项目，因为你可以拆分工作根据第 5 大项的位置将数组分成两部分），而不是迭代一次以创建新数组，然后再进行五次。

于 2013-02-07T21:40:25.117 回答
0

如前所述，排序是 O(nlogn +5) 在 O(5n + 5) 中迭代。在一般情况下，使用排序算法找到 m 个最大数是 O(nlog +m)，而迭代算法是 O(mn +m)。哪种算法更好的问题取决于 m 和 n 的值。对于 5 的值，迭代最多 2 到第 5 个数字更好，即微不足道的 32。但是就操作而言，排序比迭代更密集，所以它会更多，直到它更快。

从理论上讲，您可以通过使用迄今为止最大数字的排序 srray 和二进制搜索来保持将为您提供 O(nlogm) 的顺序，但这又取决于 n 和 m 的值。

于 2013-02-07T21:43:16.700 回答
0

也许数组不是您想要的最佳结构。特别是因为每次添加新值时都需要对其进行排序。也许链表更好，在插入时进行排序（在最坏的情况下是 O(N)，在最好的情况下是 O(1)），然后丢弃最后五个元素。此外，您必须考虑仅切换一个指针比重新分配整个数组要快得多，只是在其中获取另一个元素。

为什么不是 AVL 树？遍历时间为 O(log2N)，但您必须考虑重新平衡树的时间，以及花在编码上的时间是否值得。

于 2013-02-07T21:57:38.033 回答
0

使用min-heap数据结构并将堆大小设置为5，当堆的最小元素小于数组中的元素时，您可以遍历数组并插入堆。 getMin需要O(1)时间，插入需要O(log(k))时间k堆的元素大小在哪里（在我们的例子中是5）。所以在最坏的情况下，我们O(n*log(k))很难找到最多 5 个元素。另一个O(n)将获取排除列表。

于 2013-02-07T22:46:35.250 回答