题目描述
给定一个长度为n的整数数列,以及一个整数k,请用快速选择算法求出数列从小到大排序后的第k个数。
blablabla
样例
int n = 5 k = 3;
int[] nums = new int[]{2 4 1 5 3}
blablabla
import java.util.Random;
import java.util.Scanner;
class Main{
static Random random = new Random();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) nums[i] = sc.nextInt();
System.out.print(findKthSmallestNum(nums, k));
}
public static int findKthSmallestNum(int[] nums, int k) {
return quickSelect(nums, k, 0, nums.length - 1);
}
public static int quickSelect(int[] nums, int k, int left, int right) {
if (left == right) return nums[left];
int randomIndex = random.nextInt(right - left + 1) + left;
int target = nums[randomIndex];
swap(left, randomIndex, nums);
int i = left - 1, j = right + 1;
while (i < j) {
while (nums[++i] < target);
while (nums[--j] > target);
if (i < j) swap(i, j, nums);
}
int length = j - left + 1;
if (k <= length) return quickSelect(nums, k, left, j);
return quickSelect(nums, k - length, j + 1, right);
}
public static void swap(int i, int j, int[] nums) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla