Оптимален ли алгоритм и удовлетворяет ли он заданной сложности? - PullRequest
Новая
       95

Оптимален ли алгоритм и удовлетворяет ли он заданной сложности?

0 голосов
/ 21 июня 2020

Символы данной строки должны быть отсортированы в соответствии с порядком, определенным другой строкой образца. Требования к сложности O (n + m) , где n - длина строки, а m - длина шаблона.

Пример:

Шаблон: 1234567890AaBbCcDdEeFfGgHh

Строка: dH7ee2D6a341Fb9Ea20dhC1g7ca32Ba2Gac5f76A2g

Результат: 112222233456677790AaaaaaBbCccDddEeeFfGggHh

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

Мой код: 

// Instances of possible values ​​for input:
String pattern = "1234567890AaBbCcDdEeFfGgHh";
String string = "dH7ee2D6a341Fb9Ea20dhC1g7ca32Ba2Gac5f76A2g";

// Builder to collect characters for sorted result:
StringBuilder result = new StringBuilder();

// Hash table based on characters from pattern to count occurrence of each character in string:
Map<Character, Integer> characterCount = new LinkedHashMap<>();

for (int i = 0; i < pattern.length(); i++) {
    // Put each character from pattern and initialize its counter with initial value of 0:
    characterCount.put(pattern.charAt(i), 0);
}

// Traverse string and increment counter at each occurrence of character
for (int i = 0; i < string.length(); i++) {
    char ch = string.charAt(i);
    Integer count = characterCount.get(ch);
    characterCount.put(ch, ++count);
}

// Traverse completed dictionary and collect sequentially all characters collected from string
for (Map.Entry<Character, Integer> entry : characterCount.entrySet()) {
    Integer count = entry.getValue();

    if (count > 0) {
        Character ch = entry.getKey();

        // Append each character as many times as it appeared in string
        for (int i = 0; i < count; i++) {
            result.append(ch);
        }
    }
}

// Get final result from builder
return result.toString();

Оптимален ли этот код? Есть ли способ улучшить этот алгоритм? Правильно ли я понимаю, что он удовлетворяет заданной сложности O (n + m)?

1 Ответ

1 голос
/ 21 июня 2020

Не уверен, ваш или мой разумный выбор времени быстрее. Но вот альтернатива: 

import java.math.BigDecimal;
class Playground {
    public static void main(String[ ] args) {
        String pattern = "1234567890AaBbCcDdEeFfGgHh";
        String s = "dH7ee2D6a341Fb9Ea20dhC1g7ca32Ba2Gac5f76A2g";
        long startTime = System.nanoTime();
        StringBuilder sb = new StringBuilder();

        for (char c : pattern.toCharArray()) {
            sb.append(s.replaceAll("[^" + c + "]", ""));
        }

        System.out.println(sb.toString());

        BigDecimal  elapsedTime =
            new BigDecimal( String.valueOf(System.nanoTime() - startTime)
                          )
        .divide(
            new BigDecimal( String.valueOf(1_000_000_000)
                          )
        );
        System.out.println(elapsedTime + " seconds");
    }
}

Объяснение:

Для каждого символа в шаблоне используйте метод replaceAll на основе регулярного выражения String, чтобы заменить все символы, кроме текущего, пустой строкой. Промыть и повторить. Это оставит вам количество каждого символа в оригинале без изменений, упорядоченное по последовательности символов шаблона.

Выводы: 

112222233456677790AaaaaaBbCccDddEeeFfGggHh
0.021151652 seconds

(Время несколько субъективно. Оно взято с Sololearn Java Playground. Очевидно, это зависит от текущей нагрузки на их серверы)

...