Блог пользователя Mehrdad12

Автор Mehrdad12, 11 лет назад, По-английски

Hi all, I just write my solution to solve problem 285C. but i has "Time limit exceeded on test 8" error, but another person wrote a solution like mine, but it doesn't have this probelm, what's wrong? thanks for any help. my code:

public class Main {
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner sc=new Scanner(System.in);
        PrintWriter pw=new PrintWriter(System.out);
        long c=0;
        int n=sc.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++)
            a[i]=sc.nextInt();
        Arrays.sort(a);
        for(int i=0;i<n;i++)
            c+=Math.abs(a[i]-(i+1));
        pw.print(c);
        pw.flush();
    }
}

other guy's code:

public class Contest {
    public static void main (String [] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);        
        int n = in.nextInt();
        List <Integer> aa = new ArrayList <Integer> ();
        int [] a = new int[n];
        int t  = 7;
        long counter = 0;
        for(int i = 0; i < n; ++i) {
            a[(i + t) % n] = in.nextInt();
        }
        Arrays.sort(a);
        for(int i = 0; i < n; ++i){
            counter += Math.abs((i + 1) - a[i]);
        }
        out.println(counter);
        out.flush();
    } 
}
  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

I'm not so sure, but I think that the worst case performance for Array.sort() is O(N²) in a really special case. That's why the second algorithm doesn't get TLE, because he changes the initial order of the array and the special case now is gone. I think that was discussed here before. Anyway, you should always shuffle your array before sorting it in Java.

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I think this thread answers your question. When using objects java uses Tim sort and for primitive data types it uses dual pivot quick sort. As Mdantas said some special input case causes Arrays.sort() to go in O(n^2) while Tim sort even in worst case uses O(n*log(n)).