如何在未排序的只读数组中找到第K个最小整数？ [英] How to find the Kth smallest integer in an unsorted read only array?

问题描述

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

This is a standard question which has been answered many a times in several sites but in this version there are additional constraints:

1. 数组是只读的（我们不能修改数组）。


2. 在O（1）空间中做。

有人可以向我解释一下吗？

Can someone please explain to me the approach to this in best possible time complexity.

推荐答案

实际上，有一种方法可以解决 O（n log d）时间复杂度& O（1）空间复杂度，无需修改数组。这里的 n 代表数组的长度，而 d 则是其中包含的数字范围的长度。

There is actually one way of solving this problem in O(n log d) time complexity & O(1) space complexity, without modifying the array. Here n stands for the length of the array, while d is the length of the range of numbers contained in it.

这个想法是对第k个最小的元素执行 binary search 元件。从lo =最小元素开始，然后hi =最大元素开始。在每个步骤中，检查多少个元素小于中点，并相应地进行更新。这是我的解决方案的Java代码：

The idea is to perform a binary search for the kth smallest element. Start with lo = minimum element, and hi = maximum element. In each step check how many elements are smaller than mid and update it accordingly. Here is the Java code for my solution:

    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;
    }

请注意，此解决方案也适用于具有重复和/或负数的数组。

Note that this solution also works for arrays with duplicates and/or negative numbers.

这篇关于如何在未排序的只读数组中找到第K个最小整数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！