congege @ 2023-05-07 20:50:50
import java.io.*;
/**
* @Author congge
* @Date 2023/5/7 10:01
* @description https://www.luogu.com.cn/problem/P1923
* 求第 k 小的数(快速排序的变种)
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer tokenizer = new StreamTokenizer(reader);
tokenizer.nextToken();
int n = (int) tokenizer.nval;
tokenizer.nextToken();
int k = (int) tokenizer.nval;
int[] array = new int[n];
for (int i = 0; i < n; i++) {
tokenizer.nextToken();
array[i] = (int) tokenizer.nval;
}
Main main = new Main();
main.quickSortByK(array, 0, n - 1, k);
// Arrays.sort(array);
// System.out.println(Arrays.toString(array));
PrintWriter printWriter = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
printWriter.println(array[k]);
// System.out.println(array[k]);
printWriter.flush();
printWriter.close();
reader.close();
}
public void quickSortByK(int[] array, int left, int right, int k) {
int mid = left + (right - left) / 2;
int i = left;
int j = right;
do {
while (array[i] < array[mid]) i++;
while (array[j] > array[mid]) j--;
if (i <= j) {
swap(array, i, j);
i++;
j--;
}
} while (i <= j);
if (k <= j) {
quickSortByK(array, left, j, k);
} else if (k >= i) {
quickSortByK(array, i, right, k);
}
}
public void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
by YoulanJun @ 2023-05-12 23:00:31
哥,有突破了能回我一下吗,我也Java这么做的,不实在知道怎么改了
by Molie @ 2023-05-29 20:47:56
此时,一个使用parallelSort()的java吊毛看着最后两个TLE掉的点陷入了沉思