如何在 QuickSelect 中实现重复

Question

我做了快速选择算法，就是在一个数组中找到第k个最小的数。我的问题是，它只适用于没有重复的数组。如果我有一个数组

arr = {1,2,2,3,5,5,8,2,4,8,8}

它会说第三小的数字是 2，但实际上是 3。

我被困在做什么，这是我的两个方法 quickSelect 和 Partition：

private int quickselect(int[] array, int leftIndex, int rightIndex, int kthSmallest) {

    if(kthSmallest > array.length - 1){

        System.out.print("Number does not exist. Please enter a number less than: ");

        return array.length - 1;

    }

    if (leftIndex == rightIndex) {

        return array[leftIndex];

    }

    int indexOfPivot = generatePivot(leftIndex, rightIndex);

    indexOfPivot = quickSelectPartition(array, leftIndex, rightIndex, indexOfPivot);

    if (kthSmallest == indexOfPivot) {

        return array[kthSmallest];

    } else if (kthSmallest < indexOfPivot) {

        return quickselect(array, leftIndex, indexOfPivot - 1, kthSmallest);

    } else {

        return quickselect(array, indexOfPivot + 1, rightIndex, kthSmallest);

    }

}

private int quickSelectPartition(int[] array, int left, int right, int pivotIndex) {

    int pivotValue = array[pivotIndex];

    swapIndexes(array, pivotIndex, right);

    int firstPointer = left;

    for(int secondPointer = left; secondPointer < right; secondPointer++) {

        if(array[secondPointer] < pivotValue) {

            swapIndexes(array, firstPointer, secondPointer);

            firstPointer++;

        }

    }

    swapIndexes(array, right, firstPointer);

    return firstPointer;

}

Answer 1

如果增加2×N运行时间是可以接受的，您可以首先将不同的元素复制到一个新数组中：private int[] getDistinct(int[] array) {&nbsp; &nbsp; Set<Integer> distinct = new HashSet<>();&nbsp; &nbsp; int endIdx = 0;&nbsp; &nbsp; for (int element : array) {&nbsp; &nbsp; &nbsp; &nbsp; if (distinct.add(element)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; array[endIdx++] = element;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return Arrays.copyOfRange(array, 0, endIdx);}然后对此进行快速选择：int[] arr = new int[] {1, 2, 2, 3, 5, 5, 8, 2, 4, 8, 8};int kthSmallest = 6;int[] distinctArray = getDistinct(arr);int kthSmallestElement = quickselect(distinctArray, 0, distinctArray.length - 1, kthSmallest - 1);System.out.println(kthSmallestElement);输出：8