用于查找无序数组的第n个排序子数组的算法是什么？

Question

我最近在一次采访中遇到了这个问题而且我失败了,现在寻找答案.

1. 假设我有一个很大的n个整数数组,所有的不同.

2. 如果这个数组是有序的,我可以将它细分为x个较小的数组,全部大小为y,除了最后一个,可能更少.我可以提取第n个子阵列并将其返回,已经排序.

示例:数组4 2 5 1 6 3.如果y = 2且我想要第二个数组,那么它将是3 4.

现在我所做的只是对数组进行排序并返回第n个子数组,它采用O(n log n).但有人告诉我,有一种方法可以做到这一点O(n + y log y).我在互联网上搜索并没有找到任何东西.想法？

Answer 1

您正在寻找的算法是选择算法,它允许您在线性时间内找到第k阶统计量.该算法非常复杂,但标准C++库可以方便地提供它的实现.

找到采访者想到的第k个排序区间的算法是这样的:

• 查找b=(k-1)*yO(N)中的订单统计信息
• 查找e=k*yO(N)中的订单统计信息
• 和y之间会有数字.将它们存储在单独的大小数组中.此操作需要O(N)bey
• y对O(y*log ₂ y)成本的大小数组进行排序.

总成本为O(N + N + N + y*log ₂ y),即O(N + y*log ₂ y)

Answer 2

你可以结合std::nth_element并std::sort为此:

std::vector<int> vec = muchData();
// Fix those bound iterators as needed
auto lower = vec.begin() + k*y;
auto upper = lower + y;

// put right element at lower and partition vector by it
std::nth_element(vec.begin(), lower, vec.end());
// Same for upper, but don't mess up lower
std::nth_element(lower + 1, upper - 1, vec.end());
// Now sort the subarray
std::sort(lower, upper);

[lower, upper) 现在是长度为y的第k个排序子阵列,平均具有所需的复杂度.

要检查y = 1真实世界使用之前的特殊情况,但这是一般的想法.