大佬,救救萌新

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 16:30:05

这题复杂度要求 O(n),如果不是非常神仙的卡常一般来说 O(n\log n) 的都过不了。


by FerventTemp0 @ 2020-07-22 16:30:18

而且 Java 好像自带大常数?


by Earthcomputer @ 2020-07-22 16:30:28

Java看不懂


by konjacq @ 2020-07-22 16:31:25

没用过java,但是听说java跑得慢?


by konjacq @ 2020-07-22 16:32:09

@impuk 这个n\lg n正常常数不可能过不了吧


by FerventTemp0 @ 2020-07-22 16:33:45

@konjacq n log n正常常数过不了,要特意卡常才能过吧


by konjacq @ 2020-07-22 16:48:05

@impuk 才22\times5\times10^6也就大概10^8没必要特意卡常吧,最多一个快读


by FerventTemp0 @ 2020-07-22 16:50:07

Java 跑 10^8 感觉有点难跑的样子


by Clannad111 @ 2020-07-22 16:58:10

@impuk java是自带大数的,但是跟这个有什么关系吗?我不太懂,因为这个是求排序的


by Clannad111 @ 2020-07-22 16:58:46

@konjacq 这个确实,java好像跑的比较慢,之前的一道题c+过了,java没过


| 下一页