Почему ошибка времени выполнения для 2 из 8 случаев?

Question

Я завершил Hackerrank's "Birthday Cake Candles" challenge и прошел 6 из 8 тестов, используя следующий код, который сортирует массив, затем увеличивает частоту, что максимальная ИНТ происходит и печатает, которые ценят:

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 

public class Solution { 

    public static void main(String[] args) { 
     Scanner in = new Scanner(System.in); 
     int numCandles = in.nextInt(); 
     int height[] = new int[numCandles]; 
     for(int height_i=0; height_i < numCandles; height_i++){ 
      height[height_i] = in.nextInt(); 
     } 

     //Option 2: Sort the array, then count the number that are highest. 
     Arrays.sort(height); 
     int max = height[height.length - 1]; 
     int index = height.length - 1; 
     int freq = 0; 
     while(height[index] == max) { 
      freq++; 
      index--; 
     } 
     System.out.println(freq); 
    } 
} 

Это не проходит тест Дело № 6 (input) или тестовый пример № 7. Короче говоря, тестовый случай № 6 - 100 000 случаев int 999999, а тестовый случай № 7 - 100 000 случаев int 1. Ожидаемый выход для обоих должен быть 100000.

Я думаю, что это может столкнуться с runtime error из-за метода сортировки, который я вызываю в массиве, и массив, пытающийся снова и снова сортировать ints равного значения? Может ли кто-нибудь объяснить, почему мой код не будет работать для этих двух тестовых случаев?

Answer 1

Когда все значения на входе являются таким же, как на входе образца Вы включили условие в этом цикле будет true до index уменьшаются до -1, в какой момент вы получите ArrayIndexOutOfBoundsException:

while(height[index] == max) { 
    freq++; 
    index--; 
} 

Добавить проверку диапазона в условия цикла, например:

while (index >= 0 && height[index] == max) { 

с этим изменением, так Все экзамены пройдут. Но это неэффективное решение. Вы отсортировали вход для уменьшения количества итераций в цикле while. Но сортировка - это операция O(n log(n)), которая медленнее, чем простая фильтрация с O(n). Например:

int numCandles = in.nextInt(); 
int heights[] = new int[numCandles]; 
int m = Integer.MIN_VALUE; 
for (int i = 0; i < numCandles; i++) { 
    heights[i] = in.nextInt(); 
    m = Math.max(m, heights[i]); 
} 

final int max = m; 
long freq = IntStream.of(heights).filter(x -> x == max).count(); 
System.out.println(freq); 

Answer 2

Вы получаете исходящую исключения, потому что вы достигаете часть, когда вы идете меньше, чем 0

while(height[index] == max) { 

    freq++; 
       if(index == 0) 
     break; 
    index--; 
} 

Это мое решение этой проблемы

Scanner in = new Scanner(System.in); 
     int n = in.nextInt(); 
     int height[] = new int[n]; 
     for(int height_i=0; height_i < n; height_i++){ 
      height[height_i] = in.nextInt(); 
     } 
     Arrays.sort(height); 
     int counter = 0; 
     int different = height[n-1]; 
     for(int height_i=n-1; height_i >=0 ; height_i--){ 

      if(different ==height[height_i]) 
      { 
      counter = counter + 1; 


      } 
      else 
       { 
       break; 
      } 

     } 
     System.out.println(counter); 
    } 

Это мое решение для этого. Я думаю, что лучше использовать для этого какое-то время.