寻找一个既不是kth最大值也不是kth最小的元素的时间复杂度？

Question

存在不按排序顺序给出的N不同数。选择一个数字需要多长时间，比如，它既不是k-最小，也不是k-最大。

我试过像这样的=>

取初始k+1数字，在O(k日志k)中对它们进行排序。然后在排序列表中获取kth数，这既不是kth最小值，也不是kth最大值。

因此，时间复杂度= 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‘’th最大或最小的元素--因此我们可以在O(1)时间内选择任何元素(例如，第一个)。

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

该算法可以在O(M)时间内找到M值的中值，因此该算法在O(k)时间内运行。

我相信对于大型N来说，这是渐近最优的--任何考虑小于k项的算法都不能保证它选择的数字不是整个数组中的kth、min或最大值。

如果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))。

Answer 2

我认为在你的解决方案中必须注意到以下几点：

首先，它需要在解决方案中使用2k+1元素而不是k+1。更具体地说，你采取：

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

Take initial 3 numbers or subarray = 3,9,1 and sorted subarray will be = 1,3,9

Now pick up 2nd element 3. Now, 3 is not the 2nd minimum nor 2nd maximum .

但是要检查这个3 is not the 2nd minimum nor 2nd，您不能使用k+1元素：subarray = 3,9,1必须检查数组以查看2、max和min是什么，并检查您的解决方案。

另一方面，通过接受2k+1元素并对它们进行排序，由于您的元素是不同的，您将知道k+1元素从k第一元素中更大，从排序子数组的k最后一个元素中更小。

在您的示例中，您可以看到：

array[] = {3,9,1,2,6,5,7,8,4} subarray[]={3,9,1,2,6}然后对子数组进行排序:{1,2,3,6,9}，并给出数字3作为回答。

例如，您的解决方案将不是array[]：= {9,8,2,6,5,3,7,1,4}，其中算法将返回数字2，即第二分钟。

就复杂性而言，.By采用2k+1元素，它不会改变您发现的复杂性，因为它将是O((2k+1)log(2k+1))，即O(klog(k))。

显然，如果n<2k+1上的算法不能工作，那么必须对整个数组进行排序，这将占用nlog n，但在本例中，n<2k+1是O(klogk)。

最后，基于上面的算法是O(klog k) .A问题，可能会混淆的是，问题有两个参数k，n .If K比n小得多，这是一种有效的算法，因为您不需要查看和缩短n个大小的数组，但是当k，n非常接近时，它与排序n大小数组是一样的。

另外一件你应该理解的事情是，大O表示法是测量当输入n给算法时的时间复杂度的方法，并显示了大输入n的算法的渐近性。O(1)表示该算法运行的是恒定时间的，最后是.So：

Now, time complexity = O(k lg k) = O(2 lg 2) = O(1).

这是不对的，你必须用k作为输入变量而不是常数来度量复杂度，这表明了随机输入k的算法的行为，很明显，上面的算法不需要O(1) (或其他恒定时间)，它需要O(k log(k))。

最后，在寻找一个更好的方法之后，如果你想要一种更有效的方法，你可以在O (n ) (n是数组的大小) .And中找到kth min和kth max，在O(n)中有一个循环，您可以简单地选择与kth min和max不同的第一个元素。我认为O(n)是自求kth、min和max取最少O(n)以来所能得到的最低时间复杂度。

关于如何在O(n)中找到kth，max，您可以在这里看到：如何在O(n)中长度为n的未排序数组中找到kth最大元素？

这个解是O(n)，而以前的解对于接近n的k参数是O(klog k) .Now，正如上面所解释的，它与O(n log(n))相同，因此，在这种情况下，O(n)解是更好的.But，如果大多数时间k比n小，那么O(k log k)可能是更好的.The解，O(n)解(第二解)的好处是在所有情况下它都需要O(n)而不考虑k，所以它是更稳定的，但是就小k而言，第一解可能更好(但在最坏的情况下它可以达到O(nlogn))。

Answer 3

您可以使用基排序按照伪线性时间对整个列表进行排序，并在恒定时间内选择k个最大元素。

总之，假设基数的大小比n小得多，或者您使用的是选择算法，这将是一个最坏的O(n)算法。

O(n)是这里的绝对下界。没有比线性更好的方法了，因为如果列表没有排序，您至少需要检查所有内容，否则您可能会错过要查找的元素。