Как можно оптимизировать данную программу?

Question

[hellcaster]

Привет. У меня есть вот такая программа, но она исполняется слишком медленно. У меня есть ограничение в 1 сек и 256 MiB. Но моя программа исполняется за 1.015 сек. Как можно ее ускорить? Возможно есть что-то такое, что сразу
бросается в глаза.

Если кому-то интересно примеры входных данных

1 тест:
4 3
4 4 7 4
Результат:
4 4 4 7 или 7 4 4 4

2 тест:
7 3
3 2 1 7 4 2 1
Результат:
Oh sh*t

package mariaAndSweets;

import java.util.Collections;
import java.util.LinkedList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

final class Main {
	static final Scanner scanner = new Scanner(System.in);
	
	public static void main(String[] args) {
		final int number = scanner.nextInt(), min = scanner.nextInt();
		LinkedList<Integer> sweets = new LinkedList<>();
		LinkedList<Integer> copy = new LinkedList<>();
		
		for (int i = 0; i < number; i++) 
			sweets.add(scanner.nextInt());
		scanner.close();

		Set<Integer> set = new HashSet<>(sweets);
		copy.addAll(set);
		
		for (int i = 0; i < copy.size(); i++) {
			if (Collections.frequency(sweets, copy.get(i)) >= min) {
				Collections.sort(sweets);
				StringBuilder sb = new StringBuilder();
				
				for (Integer j : sweets)
					sb.append(j + " ");
				
				System.out.print(sb);
				return;
			}
		}

		System.out.print("Oh sh*t");
	}
}

Comments

[Marat Khayrutdinov]

Если бы вы еще сказали, что от программы ожидается, было бы совсем здорово )

[hellcaster]

Marat Khayrutdinov, если кратко, то первое число (number) - количество конфет, второе число (min) - минимальное количество конфет, которое должно быть одного типа. В 2 строке вводиться number чисел. i число имеет тип Ai.
Если вы понимаете английский или украинский, то вот задание. Если среди этих конфет есть как минимум min одного типа, то нужно вывести так, чтобы эти конфеты одного типа шли вместе, если так невозможно сделать, нужно вывести "Oh sh*t"

Answer 1

[Александр Опарин]

she won't accept the gift if there are no k consecutive candies of the same type

Для этого не обязательно сортировать весь список

Да и вместо Collections.frequency можно сразу при вводе считать каких сколько

Answer 2

[Marat Khayrutdinov]

Может быть так будет быстрее?

LinkedList<Integer> sweets = new LinkedList<>();
    StringBuilder sb = new StringBuilder();
    AtomicBoolean hasMinAmount = new AtomicBoolean(false);
    sweets.stream()
            .collect(Collectors.toMap(Integer::intValue, integer -> 1, Math::addExact))
            .forEach((candyName, amount) -> {
              if (amount >= min) {
                hasMinAmount.set(true);
              }
              for (int i = 0; i < amount; i++) {
                sb.append(candyName + " ");
              }
            });
    if (hasMinAmount.get()) {
      System.out.print(sb);
    } else {
      System.out.println("Oh sh*t");
    }

Comments

[hellcaster]

Я стесняюсь спросить, но вместо чего это вставлять и что это такое?

[Marat Khayrutdinov]

Про проверку забыл. Виноват

[Marat Khayrutdinov]

muryn.official, вместо

Set<Integer> set = new HashSet<>(sweets);
    copy.addAll(set);
    
    for (int i = 0; i < copy.size(); i++) {
      if (Collections.frequency(sweets, copy.get(i)) >= min) {
        Collections.sort(sweets);
        StringBuilder sb = new StringBuilder();
        
        for (Integer j : sweets)
          sb.append(j + " ");
        
        System.out.print(sb);
        return;
      }
    }

    System.out.print("Oh sh*t");

[Marat Khayrutdinov]

У вас очень часто происходить сортировка
Collections.sort(sweets);
При большом массиве данных, если условие будет срабатывать часто, то вы будете дергать сортировку попусту.

[hellcaster]

Marat Khayrutdinov,

хорошо, но как это называется?

sweets.stream()
            .collect(Collectors.toMap(Integer::intValue, integer -> 1, Math::addExact))
            .forEach((candyName, amount) -> {
              if (amount >= min) {
                hasMinAmount = true;
              }
              for (int i = 0; i < amount; i++) {
                sb.append(candyName + " ");
              }
            });

Я Java не давно начал изучать. И еще мне Eclipse подсказывает, что Local variable hasMinAmount defined in an enclosing scope must be final or effectively final

[hellcaster]

Marat Khayrutdinov, У меня там стоит return. Если условие сработало, то оно 1 раз сортирует и программа заканчивается

[Marat Khayrutdinov]

Точно. Он правильно говорит. Ее можно вынести в AtomicBoolean. А то, что я написал, называется функциональный стиль. Это стримы. Но если для вас это пока сложновато, лучше обойтись простым вынесением сортировки за пределы цикла.

[Marat Khayrutdinov]

muryn.official, да, верно. Не заметил.
Хм. Еще, из того, что может замедлять работу - это перекладывания в коллекций.
Вот этот шаг - Set set = new HashSet<>(sweets); явно лишний, если бы copy уже был сетом.

[Marat Khayrutdinov]

Collections.frequency тоже дорогая операция. Вы каждый раз вынуждены перечитать всю коллекцию, чтобы посчитать количество вхождений. В моем примере всего 1 проход по изначальной коллекции. И второй проход по коллекции сплющенной в мапу

[hellcaster]

Marat Khayrutdinov, а какой смысл выносить за пределы цикла, если там стоит return? Если я нашел этот тип конфет, то оно 1 раз сортирует, выведет на экран и сразу закончит программу. Я ж все правильно понимаю?

[Marat Khayrutdinov]

muryn.official, все верно. Я отписался выше, что не заметил return'а.
Сейчас самая дорогая операция у вас получается Collections.frequency в цикле