如何在未排序的只读数组中找到第K个最小整数？

Question

这是一个标准问题,已在多个站点中多次回答,但在此版本中还有其他限制:

1. 该数组是只读的(我们无法修改数组).
2. 在O(1)空间中进行.

有人可以在最佳的时间复杂性中向我解释这种方法.

Answer 1

实际上有一种方法可以在O(n log d)时间复杂度和O(1)空间复杂度中解决这个问题,而无需修改数组.这里n表示数组的长度,而d是包含在其中的数字范围的长度.

想法是对第k个最小元素执行二进制搜索.从lo = minimum元素开始,hi =最大元素.在每个步骤中,检查有多少元素小于mid并相应地更新它.这是我的解决方案的Java代码:

    public int kthsmallest(final List<Integer> a, int k) {
        if(a == null || a.size() == 0)
             throw new IllegalArgumentException("Empty or null list.");
        int lo = Collections.min(a);
        int hi = Collections.max(a);

        while(lo <= hi) {
            int mid = lo + (hi - lo)/2;
            int countLess = 0, countEqual = 0;

            for(int i = 0; i < a.size(); i++) {
                if(a.get(i) < mid) {
                    countLess++;
                }else if(a.get(i) == mid) {
                    countEqual++;
                }
                if(countLess >= k) break;
            }

            if(countLess < k && countLess + countEqual >= k){
                return mid;
            }else if(countLess >= k) {
                hi = mid - 1;
            }else{
                lo = mid + 1;
            }
        }


        assert false : "k cannot be larger than the size of the list.";
        return -1;
    }

请注意,此解决方案也适用于具有重复和/或负数的阵列.

Answer 2

我将假设只读数组是一个强烈要求,并尝试在此答案中找到不违反它的权衡(因此,使用选择算法不是一个选项,因为它修改了数组)

作为旁注,来自维基百科,在不修改数组的情况下无法在O(1)空间中完成:

选择所需的空间复杂度很容易看出是k + O(1)(或者如果k> n/2则为n - k),并且就地算法可以选择只有O(1)额外存储....可以以仅获得近似答案或以一定概率正确答案为代价来降低空间复杂度

它可以在O(k)空间中以O(nlogk)时间完成.如果k是不变的,那就是O(1)解决方案

这个想法是保持最大的堆大小k.首先用第一个k元素填充它,然后继续迭代数组.如果某个元素x小于堆的顶部,则弹出旧头,然后插入x.

完成后,堆的头部是k最小的元素.

在大O表示法的观点出发,可以在完成O(n)与O(k)空间通过使用大小的新的数组2k,在组块到阵列负载元件,并使用选择算法此auxillary阵列上找到k个元素.丢弃大于第k个元素的所有元素,并重复下一个块(加载更多k元素).复杂性是O(k*n/k) = O(n)

然而,这很少使用,并且具有比堆解决方案明显更差的常量,堆解决方案经常使用.

如果你真的想使用O(1)空间,可以通过找到最小k时间来使用强力解决方案.你只需要记住旧的最小值,即恒定的空间.该解决方案是O(nk)具有O(1)空间的时间,其在时间方面明显低于替代方案.