找出数组中第 k 个小的元素

可以使用快速选择算法来找到数组中第 k 个小的元素。

快速选择算法的基本思想和快速排序类似，它也是利用分治的思想来解决问题的。具体步骤如下：

1. 选定数组中的一个元素作为基准值（pivot）。
2. 将数组中小于基准值的元素放在左边，大于基准值的元素放在右边，相等的元素任意放置。
3. 比较基准值所在的位置和 k 的大小关系，如果相等，返回基准值；如果小于 k，从右边继续查找；如果大于 k，从左边继续查找。

代码实现：

public static int findKthSmallest(int[] nums, int k) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == k - 1) {
            return nums[pivotIndex];
        } else if (pivotIndex < k - 1) {
            left = pivotIndex + 1;
        } else {
            right = pivotIndex - 1;
        }
    }
    return -1; // 数组中不存在第 k 个小的元素
}

private static int partition(int[] nums, int left, int right) {
    int pivot = nums[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= pivot) { // 从右往左找第一个小于 pivot 的元素
            j--;
        }
        nums[i] = nums[j];
        while (i < j && nums[i] < pivot) { // 从左往右找第一个大于等于 pivot 的元素
            i++;
        }
        nums[j] = nums[i];
    }
    nums[i] = pivot;
    return i;
}

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