大きな配列を操作する際のパフォーマンスを向上させる方法は？

Question

私はHackerrankの問題を今解決していますが、私の論理は多かれ少なかれ正しいと信じていますが、大規模なデータセットはパフォーマンスを落として「間違った」答えを与えています。あなたはそれをチェックアウトすることができますので、ここでの問題へのリンクは次のとおりです。

https://www.hackerrank.com/challenges/qheap1

私は大きなデータセットを可能にするように、このスクリプトのパフォーマンスを向上する方法を疑問に思って。私はスキャナと関係がありますが、それはなぜか分かりません。

public class Solution { 
    private static final int ADD = 1; 
    private static final int DELETE = 2; 
    private static final int GET = 3; 
    private static final int TICK = 1; 
    public static void main(String[] args) { 
     /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ 
     Scanner in = new Scanner(System.in); 
     PrintStream out = System.out; 
     int n = in.nextInt(); 
     int[] heap = new int[n]; 

     int a = 0; 
     while (a < n) { 
      a = 0; 
      int q = in.nextInt(); 

      switch(q) { 
       case(ADD): 
        int nextAdd = in.nextInt(); 
        /*out.println("ADD " + next);*/ 
        int b = 0; 
        while (b < n) { 
         /*out.println(heap[b]);*/ 
         if (heap[b] == 0) { 
          heap[b] = nextAdd+TICK; 
          /*printArray(heap);*/ 
          b = n-1; 
         } 
         b++; 
        } 
        /*printArray(heap);*/ 
        break; 
       case(DELETE): 
        int c = 0; 
        int nextDelete = in.nextInt(); 
        while (c < n) { 
         if (heap[c]-TICK == nextDelete) { 
          heap[c] = 0; 
          c = n-1; 
         } 
         c++; 
        } 
        /*printArray(heap);*/ 
        break; 
       case(GET): 
        Arrays.sort(heap); 
        int d = 0; 
        while (d < n) { 
         if (heap[d] != 0) { 
          out.println(heap[d]-TICK); 
          d = n-1; 
         } 
         d++; 
        } 
        /*printArray(heap);*/ 
        break; 
      } 
      a++; 
      /*printArray(heap);*/ 
     } 
    } 

    public static void printArray(int[] ar) { 
     String str = ""; 
     for (int i : ar) { 
      str += i + " "; 
     } 
     System.out.println(str); 
    } 
} 

Answer 1

あなたのコードを見て、私は見つけることができる唯一の当面問題は、このライン

out.println(heap[d]-TICK); 

がコメントアウトされていないという事実です。これは、あなたのJavaプログラム（いいえ、スクリプトではありません）がIO操作をたくさんしていることを意味する可能性があります。そして、それらは非常にあなたのプログラムで起こっていると比較して高価です。

だから、コメントして何が起こるかを見てください。

Answer 2

ヒープを使用しない（チャレンジで必要な）主な問題は、配列の操作に時間を費やしていることです。ここで

は、すべてのテストに合格実装です：

public static void main(String[] args) { 
    final Scanner in = new Scanner(System.in); 

    final int n = in.nextInt(); 
    final PriorityQueue<Integer> q = new PriorityQueue<>(n); 
    for (int i = 0; i < n; i++) { 
     final int command = in.nextInt(); 
     switch (command) { 
     case 1: 
      q.add(in.nextInt()); 
      break; 
     case 2: 
      q.remove(in.nextInt()); 
      break; 
     case 3: 
      System.out.println(q.peek()); 
      break; 
     } 
    } 
}