大佬,救救萌新

P1923 【深基9.例4】求第 k 小的数

Clannad111 @ 2020-07-22 16:26:33

下面是我的java写的快排,过不了。。。```java import java.math.; import java.util.; import java.io.*;

public class Main {

public static void q_Sort(int[] book, int left, int right, int k) {
    if(right <= left)
        return;
    int head = left;
    int tail = right;
    int num = book[head];
    int m = head;
    while(head < tail) {
        while(tail > head && book[tail] > num)
            tail--;
        book[m] = book[tail];
        m = tail;
        while(head < tail && book[head] < num)
            head++;
        book[m] = book[head];
        m = head;
    }
    book[m] = num;
    if(m > k)
        q_Sort(book, left, m-1, k);
    else if(m < k)
        q_Sort(book, m+1, right, k);
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    int[] book = new int[n];
    for(int i=0; i<n; i++)
        book[i] = in.nextInt();
    q_Sort(book, 0, n-1, k);
    System.out.println(book[k]);
}

}


我调用库函数Arrays.sort(book)也过不了,只能拿60分。想问问怎么搞啊

by FerventTemp0 @ 2020-07-22 17:04:03

尽量写 O(n) 的吧,这题 n\log n 有点难跑。


by Clannad111 @ 2020-07-22 17:06:23

@impuk 就不太知道java怎么写O(n),毕竟在比赛的时候报名选了一种语言后是不能用另一种语言的。如果大佬会的话可以跟我讨论一下java怎么写的吗,如果嫌麻烦也没关系。


by FerventTemp0 @ 2020-07-22 17:13:24

诶,等等……


by FerventTemp0 @ 2020-07-22 17:13:43

你这个程序光读入就超时了。

请使用快一点的读入方式。


by konjacq @ 2020-07-22 17:55:32

@impuk java当然悬啊 我说的是c++


by FerventTemp0 @ 2020-07-22 18:00:09

可是 lz 用的是Java 欸


上一页 |