当前位置：首页 > news >正文

第k个数字

news 2025/6/26 10:03:39

第K个数

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

所用方法和基本原理

快速选择算法是基于快速排序思想的一种选择算法。其基本原理如下：

划分操作：选择一个基准元素（这里选择数组中间位置的元素），通过双指针法将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。
确定目标位置：统计左边部分的元素个数。如果 k 小于等于左边部分元素个数，说明第 k 小的数在左边部分，继续在左边部分进行快速选择；否则，第 k 小的数在右边部分，需要在右边部分进行快速选择，并且此时 k 的值要减去左边部分的元素个数。
递归求解：不断重复上述过程，直到找到第 k 小的数。

代码及注释

public class QuickSelect {// 快速选择函数，用于找到数组中第k小的数public static int quickSort(int[] arr, int l, int r, int k) {// 如果左右指针重合，说明只有一个元素，直接返回该元素if (l == r) return arr[l];// 选择中间位置的元素作为基准元素xint x = arr[l + (r - l >> 1)];// 初始化左指针i，指向数组起始位置的前一个int i = l - 1;// 初始化右指针j，指向数组末尾位置的后一个int j = r + 1;// 当左指针小于右指针时，继续循环进行划分while (i < j) {// 从左向右移动左指针，找到第一个大于等于基准元素的位置while (arr[++i] < x);// 从右向左移动右指针，找到第一个小于等于基准元素的位置while (arr[--j] > x);// 如果左指针仍小于右指针，说明两个指针未相遇，交换两个指针所指向的元素if (i < j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}}// 计算左边部分（包括基准元素所在位置）的元素个数int lNum = j - l + 1;// 如果k大于左边部分元素个数，说明第k小的数在右边部分，递归在右边部分查找if (k > lNum) {return quickSort(arr, j + 1, r, k - lNum);} else {// 否则，第k小的数在左边部分，递归在左边部分查找return quickSort(arr, l, j, k);}}
}

举例说明

假设有数组 arr = [3, 2, 1, 5, 6, 4]，要找第 3 小的数（即 k = 3）。

第一次划分：
- 选择基准元素 x = arr[2] = 1（中间位置）。
- 初始化 i = -1，j = 6。
- 移动 i 到位置 0（因为 arr[0] = 3 > 1），移动 j 到位置 5（因为 arr[5] = 4 > 1）。
- 交换 arr[0] 和 arr[5]，数组变为 [4, 2, 1, 5, 6, 3]。
- 继续移动 i 到位置 1（因为 arr[1] = 2 > 1），移动 j 到位置 2（因为 arr[2] = 1）。
- 此时 i = 1，j = 2，左边部分元素个数 lNum = 2 - 0 + 1 = 3。
- 因为 k = 3，所以第 k 小的数在左边部分，继续在左边部分 [4, 2, 1] 进行查找。
第二次划分：
- 选择基准元素 x = arr[1] = 2（中间位置）。
- 初始化 i = -1，j = 2。
- 移动 i 到位置 0（因为 arr[0] = 4 > 2），移动 j 到位置 1（因为 arr[1] = 2）。
- 交换 arr[0] 和 arr[1]，数组变为 [2, 4, 1]。
- 继续移动 i 到位置 1（因为 arr[1] = 4 > 2），移动 j 到位置 0（因为 arr[0] = 2）。
- 此时 i = 1，j = 0，左边部分元素个数 lNum = 0 - 0 + 1 = 1。
- 因为 k = 3，k > lNum，所以第 k 小的数在右边部分 [4, 1] 进行查找，并且 k 变为 3 - 1 = 2。
第三次划分：
- 选择基准元素 x = arr[1] = 1（中间位置）。
- 初始化 i = -1，j = 1。
- 移动 i 到位置 0（因为 arr[0] = 4 > 1），移动 j 到位置 1（因为 arr[1] = 1）。
- 交换 arr[0] 和 arr[1]，数组变为 [1, 4]。
- 继续移动 i 到位置 0（因为 arr[0] = 1），移动 j 到位置 0（因为 arr[0] = 1）。
- 此时 i = 0，j = 0，左边部分元素个数 lNum = 0 - 0 + 1 = 1。
- 因为 k = 2，k > lNum，所以第 k 小的数在右边部分 [4] 进行查找，并且 k 变为 2 - 1 = 1。
第四次划分：
- 此时数组只有一个元素 [4]，l = r = 0，直接返回 arr[0] = 4，找到第 3 小的数为 4。

方法的优劣

时间复杂度：
- 平均情况：快速选择算法平均时间复杂度为 $O (n)$ ，因为每次划分平均可以排除一半的数据。
- 最坏情况：时间复杂度为 $O(n^2)$ ，当每次选择的基准元素都是数组中的最大或最小元素时，划分会极不均匀，导致每次只能排除一个元素。
空间复杂度：
- 平均情况：空间复杂度为 $O(\log n)$ ，这是由于递归调用栈的深度平均为 $\log n$ 。
- 最坏情况：空间复杂度为 $O (n)$ ，在最坏情况下，递归调用栈的深度为 $n$ 。