java - 处理第 k 个最小分区中的重复数字

Question

我已经得到了我的分区算法和 ksmall 递归方法来计算(几乎)完全...我只是遇到了一种情况，(我相信)我的分区算法没有处理随机给定中的重复数字大批。任何其他数组和我的输出都可以完美运行。

递归和分区检查将所有小于主元的数字放置在左侧，将所有大于主元的数字放置在右侧。

如何处理随机数组中的重复数字？

这是我的代码:

private static int partition(int[] theArray, int first, int last) {
    // Returns the index of the pivot element after partitioning
    // theArray[first..last]

    int p = theArray[first]; // use the first item of the array as the pivot (p)
    int lastS1 = first; // set S1 and S2 to empty
    int lastS2 = theArray.length-1;

    while (lastS1 < lastS2) {
        for (; theArray[lastS1] < p; lastS1++) ;

        for (; theArray[lastS2] > p && lastS2 > 0; lastS2--) ;
        if (lastS1 < lastS2)
            swap(theArray, lastS1, lastS2);
    }
    swap(theArray, lastS1, lastS2);
    return lastS2;
}
public static int kSmall(int k, int[] anArray, int first, int last) {
    int pivotIndex = partition(anArray, first, last);
    int p = anArray[pivotIndex]; // p is the pivot



        if (pivotIndex == k - 1)

            return anArray[pivotIndex];
    if (p > anArray[k - 1])

        return kSmall(k, anArray, first, pivotIndex - 1);

    return kSmall(k, anArray, pivotIndex + 1, last);

编辑一些示例并进行更深入的解释:

以下是一些成功运行的示例:

array = [13 | 29 | 53 | 49 | 68 | 12 | 72 | 47 | 80 | 89]
--------------------------------------------------------------------
Please  enter an integer k, 1<=k<=10, or 'R' to refill the array: 
1
Kth smallest is: 12
With K as: 1

还有...

array = [60 | 45 | 27 | 20 | 4 | 80 | 75 | 59 | 78 | 41]
--------------------------------------------------------------------
Please  enter an integer k, 1<=k<=10, or 'R' to refill the array: 
1
Kth smallest is: 4
With K as: 1

不成功运行:

array = [68 | 77 | 32 | 54 | 30 | 83 | 68 | 76 | 64 | 30]
--------------------------------------------------------------------
Please  enter an integer k, 1<=k<=10, or 'R' to refill the array: 
5

在此数组中，有两个“30”整数，我猜测该程序由于某种原因不会移动到下一个。

感谢您提供的任何帮助!

Answer 1

首先，关于partition函数:

• 正如@teppic提到的，这个函数应该在theArray[first..last]中进行分区。因此，last 应分配给lastS2。

• 当所有数组都相同时，您的实现也会失败。在这种情况下，lastS1 和 lastS2 永远不会改变，从而导致无限循环。我建议您查看 partition 的其他实现(例如 this one - 选择快速排序，右下部分有伪代码)。

关于kSmall函数，您的条件p> anArray[k - 1]不正确。这个想法是，在进行分区后，将数组在 pivotIndex 处分成两部分。第一部分包含 pivotIndex - 1 最小元素，第二部分包含 arraySize -ivotIndex 最大元素。使用该信息，您可以确定 k 最小元素属于哪个部分:

if (pivotIndex == k - 1)
    return a[k - 1];
else if (pivotIndex > k - 1)
    return kSmall(k, a, first, pivotIndex - 1);
else
    return kSmall(k, a, pivotIndex + 1, last);