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

Question

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

我试过这样=>

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

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

示例=>

选择既不是第二最小值也不是第二最大值的数字.

array [] = {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个最大或最小元素 - 因此可以在O(1)时间内选择任何元素(例如第一个).

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

找到M个中值可以在O(M)时间内完成,因此该算法在O(k)时间内运行.

我相信这对于大N来说是渐近最优的 - 任何考虑少于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)).