Сбой программы Java с таймаутом для некоторых тестовых случаев

Question

Я тренировался на Хакерранке. Ну, вопрос довольно прост, я приложил это здесь с примером ввода. Когда я запускаю свою локальную машину с пользовательским вводом, она работает как положено. Но пока я работаю на его онлайн-платформе, иногда 2, а иногда и 3 тестовых случая терпят неудачу с исключением из-за тайм-аута. Код ниже здесь кто-нибудь может подсказать, какое улучшение необходимо?

Это решение

public static void main(String[] args) {
        int k = 3;
        List<Integer> marks = new ArrayList<Integer>();
        marks.add(20);
        marks.add(20);
        marks.add(40);
        marks.add(60);
        marks.add(20);
        marks.add(10);
        marks.add(0);
        marks.add(100);
        System.out.println(numofPrizes(k, marks));
    }
    public static int numofPrizes(int k, List<Integer> list) {
        // Write your code here
        Collections.sort(list, Collections.reverseOrder());
        List<Integer> str = new ArrayList<Integer>();
        AtomicInteger rank = new AtomicInteger(0);
        AtomicInteger count = new AtomicInteger(0);
        list.stream().forEach(x -> {
            if(!str.contains(x)){
                rank.getAndIncrement();
            }
            if(rank.get() <= k && x > 0){
                count.getAndIncrement();
            }
            str.add(x);
//          System.out.println("mark " + x + " rank " + rank.get() + " count " + count.get() );
        });
        return count.get();     
    }

Вывод:

mark 100 rank 1 count 1
mark 60 rank 2 count 2
mark 40 rank 3 count 3
mark 20 rank 4 count 3
mark 20 rank 4 count 3
mark 20 rank 4 count 3
mark 10 rank 5 count 3
mark 0 rank 6 count 3
3

Answer 1

В этом смысле также можно думать, что если входные данные могут быть большими с точки зрения размера входного массива / списка, нам следует избегать выполнения сортировки, если это возможно.

Здесь, так как может бытьтолько 100 уникальных значений для отметок, мы можем использовать этот факт и составить отсортированную карту отметок по количеству вхождений. Это займет O (N) время. или O (n log n) время для сортировки карты (максимум 100 записей)

Ключ заключается в том, чтобы избежать сортировки больших наборов данных и создания новых больших наборов данных путем копирования больших.

Answer 2

Некоторые части кода, которые вы можете улучшить, возможно, с точки зрения читабельности и производительности, могут быть:

• , вы можете использовать List.sort для точного использования API над элементамиList

  list.sort(Collections.reverseOrder());
  

• в вашем коде задействован дорогостоящий вызов метода, который обычно равен O (n ² ) операция и т. е.

  if(!str.contains(x))
  

  эта операция может быть эффективной, т.е. O (n) при выполнении за HashSet, но тогда вы также можете немного оптимизировать дополнительные накладные расходы addкак:

  Set<Integer> str = new HashSet<>();
  
  if (str.add(x)) {
      rank++; // or the use of getAndIncrement
  }
  

• в конструктиве функционального программирования, вы могли бы скорее подумать о counting значении, пока вы сортируете их в обратном порядке, а затем ограничиваете ограничение по рангу ввводя при выполнении суммы соответствующих отсчетов

  private static int numofPrizes(int k, List<Integer> list) {
      Map<Integer, Integer> valueToCount = list.stream()
              .filter(mark -> mark != 0)
              .collect(Collectors.groupingBy(Function.identity(),
                      Collectors.collectingAndThen(Collectors.counting(), Long::intValue)));
  
      return valueToCount.entrySet().stream()
              .sorted(Map.Entry.comparingByKey(Comparator.reverseOrder()))
              .limit(k)
              .mapToInt(Map.Entry::getValue)
              .sum();
  }
  

  , обратите внимание, что groupingBy здесь является O (n) операцией снова, и этополная логика может объединить меня в один конвейер следующим образом:

---

private static long numOfPrizes(int k, List<Integer> list) {
    return list.stream()
            .filter(mark -> mark != 0)
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
            .entrySet().stream()
            .sorted(Map.Entry.comparingByKey(Comparator.reverseOrder()))
            .limit(k)
            .mapToLong(Map.Entry::getValue)
            .sum();
}

Answer 3

Когда я просто меняю подход, как показано ниже, это сработало.

public static void main(String[] args) {
    int k = 3;
    List<Integer> marks = new ArrayList<Integer>();
    marks.add(20);
    marks.add(20);
    marks.add(40);
    marks.add(60);
    marks.add(20);
    marks.add(10);
    marks.add(0);
    marks.add(100);
    System.out.println(numofPrizes(k, marks));
}
public static int numofPrizes(int k, List<Integer> list) {
              list.sort(Collections.reverseOrder());
      int number = 0,counter = 1;
      int[] mark = new int[list.size()],rank = new int[list.size()];
      Map<Integer,Integer> map  = new HashMap<Integer,Integer>();   
      for (int i = 0; i < list.size(); i++) {
              map.put(list.get(i), (map.get(list.get(i)) != null) ? map.get(list.get(i)) : counter);
              mark[i] = list.get(i);
              rank[i] = (int) map.get(list.get(i));
              counter++;
              if(mark[i] > 0 && k >= rank[i]){
                      number++;
              }
      }          
      return number;   
}