algorithm - 查找既不是第 k 个最大值也不是第 k 个最小值的元素的时间复杂度？

Question

有 N 个不同的数字，它们没有按排序顺序给出。选择一个既不是第 k 个最小值也不是第 k 个最大值的数字需要多少时间？

我试过这样=>

取初始的 k + 1 个数字并在 O(k log k) 中对它们进行排序。然后在该排序列表中选择第 k 个数字，它既不是第 k 个最小值也不是第 k 个最大值。

因此，时间复杂度 = O(K log k)

例子=>

选择一个既不是第二最小值也不是第二最大值的数字。

数组[] = {3,9,1,2,6,5,7,8,4}

取最初的 3 个数字或子数组 = 3,9,1，排序后的子数组将为 = 1,3,9

现在拿起第二个元素 3。现在，3 既不是第二个最小值也不是第二个最大值。

现在，时间复杂度 = O(k lg k) = O(2 lg 2) = O(1)。

Answer 1

如果 N < k，问题就不重要了。否则数组中没有第 k 个最大或第 k 个最小元素——因此可以在 O(1) 时间内选择任何元素(例如第一个)。

如果 N 足够大，您可以取大小为 2k+1 的任何子集并选择中位数。然后你找到了一个保证不是整个数组中第 k 个最大或第 k 个最小数的数字。事实上，您得到了更强大的东西——保证它不会出现在排序数组的前 k 个或最后 k 个数字中。

找到 M 个事物的中位数可以在 O(M) 时间内完成，因此该算法在 O(k) 时间内运行。

我相信这对于大 N 是渐近最优的——任何考虑少于 k 个项目的算法都不能保证它选择的数字不是整个数组中的第 k 个最小值或第 k 个最大值。

如果 N 不够大(特别是 N < 2k+1)，您可以在 O(N) 时间内找到最小值(如果 k=1，则为第二最小值)。由于 k <= N < 2k+1，这也是 O(k)。

无解存在三种情况:(k=1, N=1), (k=1, N=2), (k=2, N=2)。

如果只考虑 k <= N 的情况，那么整个算法的复杂度就是 O(k)。如果你也想包括一些琐碎的案例，那就有点乱了。如果 I(k<=N) 是函数，当 k<=N 时为 1，否则为 0，则更严格的界限是 O(1 + k*I(k<=N))。