如何求出一个无序数组中第K小的数？

要在一个无序数组中找到第 K 小的数,可以使用快速选择算法(Quickselect)。

public int findKthSmallest(int[] nums, int k) {
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
        int partitionIndex = partition(nums, left, right);
        if (partitionIndex == k - 1) return nums[partitionIndex];
        if (partitionIndex < k - 1) left = partitionIndex + 1;
        else right = partitionIndex - 1;
    }

    return -1;
}

private int partition(int[] nums, int left, int right) {
    int pivot = nums[right];
    int partitionIndex = left;

    for (int i = left; i < right; i++) {
        if (nums[i] <= pivot) {
            swap(nums, i, partitionIndex);
            partitionIndex++;
        }
    }

    swap(nums, right, partitionIndex);
    return partitionIndex; 
}

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

算法流程:

1. 将数组下标 left 到 right 看作一个区间。
2. 选择区间最后一个数作为枢轴 pivot。
3. 从区间左边开始遍历,小于 pivot 的数停下来,将其与区间左端点互换。
4. 将 pivot 与换过来的数互换。此时 pivot 的位置就是它在区间内部的最终位置。
5. 根据 pivot 的最终位置和 k 的大小判断下一步的区间范围是在 pivot 的左边还是右边。
6. 重复上述步骤直到找到第 k 小的数。

时间复杂度 O(n),空间复杂度 O(1)。

所以,在无序数组中找到第 K 小数的关键是:

1. 使用快速排序的 partition 操作划分数组。
2. 根据 partition 结果缩小搜索区间,递归查找。
3. 特殊情况,如果数组长度为 1,直接返回。