Java中获取无序数组第n小元素时结果错误的问题排查

你的代码尝试用类似快速选择的思路找第n小元素，但存在几个关键错误导致结果不符合预期，咱们一步步拆解问题：

1. 基准值未被正确放置到分区数组中 #

你选了array[0]作为基准，但循环处理时把基准值和其他元素一起归类到了“大于等于基准”的组里，最后基准值被放到了数组末尾，没有回到它应该在的分区中间位置——这直接导致后续递归的分区逻辑完全错乱。

2. 递归时的m参数逻辑错误 #

你调用nthMin(array, 2)期望得到第2小元素（对应排序后[2,3,5,6,10,11,15]里的3），但你的代码没有正确计算基准值的排名：基准值的位置应该是左半部分元素的数量+1，而你直接用start和m比较，完全忽略了基准值本身的存在。另外，当m == start时，你错误返回了原数组的array[start]，而不是分区后数组里的基准值。

3. 基准值的循环处理逻辑错误 #

循环从i=0开始，把基准值自己也当成普通元素处理，导致它被放到了数组末尾，进一步打乱了分区结构。

修复后的代码 #

下面是修正后的版本，解决了所有问题：

import java.util.Arrays;

public class NthMinFinder {
    private static int nthMin(int[] array, int m) {
        // 假设m是从1开始计数的第m小元素
        if (array.length == 1) {
            return array[0];
        }
        
        int pivot = array[0]; // 选择第一个元素作为基准
        int start = 0;
        int end = array.length - 1;
        int[] newArray = new int[array.length];
        
        // 跳过基准值，单独处理其他元素
        for (int i = 1; i < array.length; i++) {
            if (array[i] < pivot) {
                newArray[start] = array[i];
                start++;
            } else {
                newArray[end] = array[i];
                end--;
            }
        }
        // 把基准值放到分区后的正确位置
        newArray[start] = pivot;
        
        // 基准值是第(start+1)小的元素（左半有start个更小的元素）
        if (m == start + 1) {
            return pivot;
        } else if (m < start + 1) {
            // 目标在左半部分，递归查找
            return nthMin(Arrays.copyOfRange(newArray, 0, start), m);
        } else {
            // 目标在右半部分，调整m的值后递归
            return nthMin(Arrays.copyOfRange(newArray, start + 1, newArray.length), m - (start + 1));
        }
    }

    public static void main(String[] args) {
        int[] array = {10, 2, 5, 6, 11, 3, 15};
        System.out.println(nthMin(array, 2)); // 输出3，符合预期
    }
}

关键修复点说明 #

• 单独处理基准值：循环从i=1开始，跳过基准值，最后把基准值放到newArray[start]，确保左半部分全是小于基准的元素，右半部分全是大于等于的，基准值在中间正确位置。
• 修正递归的m参数：基准值的排名是start+1（左半有start个更小的元素），根据m和这个排名的关系决定递归方向，右半部分递归时要把m减去左半和基准的总数量。
• 正确返回结果：当m匹配基准值的排名时，直接返回基准值，而不是错误地引用原数组元素。

内容的提问来源于stack exchange，提问作者Oleg Caralanski