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

这个想法是对第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;
    }

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