（Java）【深基9.例4】求第k小的数

一、题目描述

输入 $n$&＃xff08;$1\le n<5000000$ 且 $n$ 为奇数&＃xff09;个数字





a


i




a_i


ai​&＃xff08;




1


≤



a


i



<



10


9




1 \le a_i <{10}^9


1≤ai​<109&＃xff09;&＃xff0c;输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 nth_element 来写本题&＃xff0c;因为本题的重点在于练习分治算法。

二、样例输入 #1

5 1
4 3 2 1 5


三、样例输出 #1

2


四、错误经历

使用了快速排序的标准模板&＃xff0c;超时了

import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc &＃61; new Scanner(System.in);
int n &＃61; sc.nextInt();
int k &＃61; sc.nextInt();
int[] a &＃61; new int[n];
for (int i &＃61; 0; i a[i] &＃61; sc.nextInt();
}
quickSort(a, 0, n - 1);
System.out.println(a[k]);
}
public static void quickSort(int[] a, int low, int high) {
int i,j;
int temp,t;
if (low > high){
return;
}
i &＃61; low;
j &＃61; high;
//temp就是基准位
temp &＃61; a[low];
while (i //先看右边&＃xff0c;依次往左递减
while (a[j] >&＃61; temp && j > i){
j--;
}
//再看左边&＃xff0c;依次往右递增
while (a[i] <&＃61; temp && i i&＃43;&＃43;;
}
//如果满足条件则交换
if (i t &＃61; a[i];
a[i] &＃61; a[j];
a[j] &＃61; t;
}
}
//最后将基准为与i和j相等位置的数字交换
a[low] &＃61; a[i];
a[i] &＃61; temp;
//递归调用左半数组
quickSort(a,low,j - 1);
//递归调用右半数组
quickSort(a,j &＃43; 1,high);
}
}


import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc &＃61; new Scanner(System.in);
int n &＃61; sc.nextInt();
int k &＃61; sc.nextInt();
int[] a &＃61; new int[n];
for (int i &＃61; 0; i a[i] &＃61; sc.nextInt();
}
Quick_Sort(a, 0, n - 1,k);
System.out.println(a[k]);
}
public static void Quick_Sort(int arr[], int begin, int end,int k){
if(begin > end)
return;
int tmp &＃61; arr[begin];
int i &＃61; begin;
int j &＃61; end;
while(i !&＃61; j){
while(arr[j] >&＃61; tmp && j > i)
j--;
while(arr[i] <&＃61; tmp && j > i)
i&＃43;&＃43;;
if(j > i){
int t &＃61; arr[i];
arr[i] &＃61; arr[j];
arr[j] &＃61; t;
}
}
arr[begin] &＃61; arr[i];
arr[i] &＃61; tmp;
if(k &＃61;&＃61; i || k &＃61;&＃61; j) {
return;
} else if(k Quick_Sort(arr, begin, i-1,k);
}else if(k > j){
Quick_Sort(arr, j&＃43;1, end,k);
}else {
Quick_Sort(arr, i, j,k);
}
}
}


直接使用了Arrays.sort( )&＃xff0c;也超时了

import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc &＃61; new Scanner(System.in);
int n &＃61; sc.nextInt();
int m &＃61; sc.nextInt();
int[] a &＃61; new int[n];
for (int i &＃61; 0; i a[i] &＃61; sc.nextInt();
}
Arrays.sort(a);
System.out.println(a[m]);
}
}


我废了&＃xff0c;栓Q