数组中第K小的元素

Question

给定一个大小为n的数组，提供一个确定性算法（不是快速排序），使用O(1)空间（不是中位数），可以找到第K小的项。

有一些显而易见的解决方案，比如在nlogn上对数组进行排序或者在nk时间内找到最小的k次，但我相信还有更好的方法。它不必是线性的（如果可以的话我怀疑它能）。

感谢各位助手。

- Ofer Magen

---

可能会出现重复 https://dev59.com/UnVC5IYBdhLWcg3wjyDu - sigmalha

我已经说过它不能是中位数或快速排序，因为两者都是非确定性的或使用额外空间。 - Ofer Magen

归并排序和堆排序是确定性的，并且运行时间为O(n log n)。 - blazs

但不在O(1)空间内 - @blazs - Ofer Magen

Answer 1

将数组排列成最小堆（可以在 O(n) 时间内构建），以便不浪费任何额外空间，并执行 k 个提取最小值操作，每个操作需要 O(log n) 的时间。因此，总时间复杂度为 O(n + k*log n)。（由于 k <= n，所以最坏情况下为 O(n log n)。）

空间复杂度为 O(1)，如果计算修改后的数组，则为 O(n)；但是任何算法都需要该数组，并因此需要贡献数组的 O(n) 空间。堆带来的附加空间成本为 O(1)。

显然，这种方法是正确的：第一个提取最小值返回（并从堆中删除）最小元素；第二个提取最小值返回（并从堆中删除）第二小的元素；……；第 k 个提取最小值返回（并从堆中删除）第 k 小的元素。

如果 k 比 n/2 "大得多"，则可以通过使用最大堆并使用类似的方法搜索第 (n-k) 大的元素来加速。

- blazs

Answer 2

使用二分查找查找第K小的元素 :)

bool c(int a[],int l,int r,int v,int k)
{
    int cnt=0;
    for(int i=l;i<=r;i++)
    {
        
        if(a[i]<=v )
        {
            cnt++;
        }
    }
    if(cnt>=k)
    {
        return true;
    }
    return false;
}
int kthSmallest(int a[], int l1, int r1, int k)
{
    int l=a[l1],r=a[l1];
    for(int i=l1+1;i<r1;i++)
    {
        l=min(l,a[i]);
        r=max(r,a[i]);
    }
    int res=0;
 
    while(l<=r)
    {
        int mid=l+(r-l)/2;
        if(c(a,l1,r1,mid,k))
        {
            res=mid;
            r=mid-1;
        }else
        {
            l=mid+1;
        }
    }
    return res;
}

- DIPANSHU KUMAR

---

时间复杂度=O(nlogn)，空间复杂度=O(1) - DIPANSHU KUMAR

Answer 3

我发现使用BitVector是解决这个问题的另一种方法。

填充BitVector需要O(n)时间，查找第k小的元素需要大约O(k)时间。因此总复杂度将为O(n)。

空间复杂度可能根据每种情况而不同。在我的情况下，列表可以包含从1到2147483647（java.lang.Integer.MAX_VALUE）的未排序正整数集合（2147483647/32 * 4 / 1024 / 1024 =~ 255 MB）。

以下是我在Java中的实现：

int findKthSmallestInUnsortedList(List<Integer> list, int k) {
    // Step 1: Populate (read) data from list to the bit-vector in O(n) time
    int[] bitVector = new int[Integer.MAX_VALUE/32]; //4 bytes chunks (int): 32 bits
    for(Integer num : list) {
        int chunkNum = num / 32;
        int indexInChunk = num % 32;
        bitVector[chunkNum] |= (1 << indexInChunk);
    }

    // Step 2: Find the k'th '1' starting from the first chunk in O(k) time
    int count = 0;
    for (int i = 0; i < bitVector.length; i++) {
        int bitCount = 0;
        while(bitVector[i] != 0) {
            if ((bitVector[i] & 1) != 0) {
                count++;
            }
            if (count == k) {
                return i * 32 + bitCount;
            }
            bitCount++;
            bitVector[i] >>= 1;
        }
    }
    return -1; // not found
}

对于那些不熟悉BitVector的人，这里有一个例子：

假设数字4在列表中。因此，我们将第一个块中的第4位设置为1：

00000000 00000000 00000000 00001000

如果读取33，则根据上述实现，我们转到第二个块并将第一个位设置为1，依此类推。

最后，我们从BitVector开头开始计算k个1。当找到第k个1时，我们将该1的块号乘以32，并加上该块中此1的位置（i * 32 + bitCount）。

- Youness