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

Z时代
2024-01-10
分类：问答

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

该数组是只读的（我们无法修改该数组）。

在O（1）空间中执行。

有人可以在可能的最佳时间复杂度下向我解释此方法。

回答：

实际上，有一种解决时间复杂度和空间复杂度的方法，。在这里，

代表数组的长度，而是其中包含的数字范围的长度。

这个想法是对第k个最小元素执行二进制搜索。从lo =最小元素开始，然后hi =最大元素开始。在每个步骤中，检查多少个元素小于中点，并相应地进行更新。这是我的解决方案的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;
    }