在未排序的数组中查找第 k 个最小的元素

Question

我正在尝试实现以下伪代码。我只需要使用逻辑分区来执行此操作。

Procedure SELECT( k,S) 
{ if  |S| =1 then return the single element in S
   else  { choose an element a randomly from S;
          let S1,S2,and S3 be he sequences of elements in S   
          less than, equal to, and greater than m, respectively;
         if |S1| >=k then return SELECT(k,S1)
          else 
               if (|S1| + |S2| >=k then return m
               else  return SELECT(k-|S1|-|S2| , S3);
         }
}

这是我到目前为止的尝试：

public static int select(int k, int[] s, int arrayLeft, int arrayRight) {
    if (s.length == 1) {
        return s[0];
    } else {
        Random rand = new Random();
        int right = rand.nextInt(arrayRight) + arrayLeft;
        int m = s[right];
        int pivot = partition(s, arrayLeft, right); // pivot = |s1|
        if (pivot >= k) {
            return select(k, s, arrayLeft, pivot - 1);
        } else {
            // Calculate |s2|
            int s2Length = 0;
            for (int i = pivot; s[i] == m; i++) {
                s2Length++;
            }
            if (pivot + s2Length >= k) {
                return m;
            } else {
                int s3Left = pivot + s2Length;
                return select(k - pivot - s2Length, s, s3Left + 1, s.length);
            }
        }
    }
}

// all elements smaller than m are to the left of it,
// all elements greater than m are to the right of it
private static int partition(int[] s, int left, int right) {
    int m = s[right];
    int i = left;
    for (int j = left; j <= right - 1; j++) {
        if (s[j] <= m) {
            swap(s, i, j);
            i++;
        }
    }
    swap(s, i, right);
    return i;
}

private static void swap(int[] s, int i, int j) {
    int temp = s[i];
    s[i] = s[j];
    s[j] = temp;
}

我的 select 方法没有返回实际的第 k 个最小元素。分区方法只在小于 m 的元素上正确地工作。在 m 右边的数组部分，有任意值的元素。我该如何解决？我在网上看到的所有解决方案都与我的方法相同。感谢您的帮助！

Answer 1

我不确定你的代码应该如何工作的细节，但我想我发现了一些可疑点。

首先，我认为您应该准确说明方法的有效参数以及它如何使用 arrayLeft 和 arrayRight。写一个 Javadoc 注释并说明这一点。这将使您自己和其他任何人更容易争论代码中的正确和错误。

这是错误的：

    if (s.length == 1) {

您正在通过所有递归调用传递同一个数组，因此如果它从一开始就没有长度 1（微不足道的情况），它的长度永远不会为 1。而是使用 arrayLeft 和arrayRight 确定要考虑的元素数量。

这条线看起来不对：

        int right = rand.nextInt(arrayRight) + arrayLeft;

如果 arrayLeft 是 10 而 arrayRight 是 12，它可能会产生最多 21。我确实在下面的行中观察到 ArrayIndexOutOfBoundsException 一次，因为 right 指向外面数组。

此行中的注释不正确，可能会导致您对代码产生错误的论点：

        int pivot = partition(s, arrayLeft, right); // pivot = |s1|

从partition()返回的pivot是重新排序后m的索引。我认为正确的说法是pivot == arrayLeft + |s1|。请自查。

我进一步认为您不应将 right 作为上述调用中的最后一个参数传递，而应传递 arrayRight。此错误可能是您观察到 partition() 在 m.

右侧留下任何值的原因

你也可能在这里冒 ArrayIndexOutOfBoundsException 的风险：

            for (int i = pivot; s[i] == m; i++) {

您应该添加一个附加条件，例如 i <= arrayRight 或 i < s.length。

最后，这在我看来是错误的：

                return select(k - pivot - s2Length, s, s3Left + 1, s.length);

我在想：

                return select(k - pivot - s2Length, s, s3Left, arrayRight);

但请根据您自己的知识进行检查。我特别怀疑 arrayRight.

在未排序的数组中查找第 k 个最小的元素

Finding the kth smallest element in an unsorted array

java

sorting

partitioning

pseudocode