java - 了解为什么 Java 选择排名返回 max() 作为最终结果

Question

我正在为以下问题制定解决方案:

Describe an algorithm to find the smallest one million numbers in one billion numbers. Assume that the computer memory can hold all one billion numbers.

这本书给出了选择排名的解决方案，但我很难理解其中的一些部分:

public static int partition(int[] array, int left, int right, int pivot) {
    while (true) {
        while (left <= right && array[left] <= pivot) {
            left++;
        }

        while (left <= right && array[right] > pivot) {
            right--;
        }

        if (left > right) {
            return left - 1;
        } 
        swap(array, left, right);
    }
}

public static int rank(int[] array, int left, int right, int rank) {
    int pivot = array[randomIntInRange(left, right)];
    int leftEnd = partition(array, left, right, pivot); // returns end of left partition
    int leftSize = leftEnd - left + 1;
    if (leftSize == rank + 1) {
        return max(array, left, leftEnd);
    } else if (rank < leftSize) {
        return rank(array, left, leftEnd, rank);
    } else {
        return rank(array, leftEnd + 1, right, rank - leftSize);
    }
}  

大部分我都看懂了，但是上面下面两行我没看懂:

if (leftSize == rank + 1) {
            return max(array, left, leftEnd);

1. 为什么要返回三个变量中的最大值？

2. 我们不应该只返回 array[left:leftEnd] 或类似的东西吗？

Answer 1

恭喜您尝试通过仔细研究一本书来学习一些东西。这是一项似乎越来越稀有的关键技能。

如果 rank 的返回值的定义是“恰好存在一百万个小于或等于 rank 的数字”，这就具有普遍意义。 max 的定义类似于:

int t = array[left];
for (int i = left + 1; i <= leftEnd; i++) 
  t = Math.max(t, array[i]);
return t;

返回最大值超出了问题陈述的范围，而且有点奇怪。仅对元素进行分区，使最大百万位于顶部会更好、更简单:array[0] 到 array[999999]。然后仅在实际需要时才找到最大值

请注意，因为 rank 是尾递归的，所以我认为有一个相同代码的简单迭代版本会更清楚。

我也不相信这段代码是正确的。 leftSize == rank 在检查中比 leftSize == rank + 1 更有意义。但是没有更多的定义和调用代码，很难确定。