【深基9.例4】求第 k 小的数
一、题目描述
输入
n
n
n(
1
≤
n
<
5000000
1 \le n <5000000
1≤n<5000000 且
n
n
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
k
k 小的数。最小的数是第
0
0
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