FirstNonRepeatingCharacter в заданной строке In java с использованием сложности времени O (n) - PullRequest
0 голосов
/ 06 февраля 2020

если я дал строку типа "aabefddbccffaa", программа должна вернуть в строку символ firstNonRepeatingCharacter, пример вывода - "e". Временная сложность должна быть только O (n). Я пытался с HashMaps и используя массив символов.

HashMap<Character, Integer> char_counts = new HashMap(); 
for(int i=0; i<string.length(); i++) { 
    char c = string.charAt(i); 
    if(char_counts.containsKey(c)) { 
        char_counts.put(c, char_counts.get(c)+1); 
    } else { 
        char_counts.put(c, 1); 
    } 
} 
for (int i=0; i<string.length();i++) { 
    char c = string.charAt(i); 
    if (char_counts.get(c) == 1) {
         return c; 
    }
} 
return ''; 

[Примечание] Если FirstNonRepeatingCharacter не найден, просто верните '';

Ответы [ 2 ]

2 голосов
/ 06 февраля 2020

Кажется, вас беспокоит второй l oop, хотя он не влияет на O(n) асимптоту c сложность времени.

Вы все еще можете от него избавиться.

Например, вместо того, чтобы находить частоту каждого символа, вы можете сохранить два Set s - первый - all - содержит все отдельные символы. Второй - uniques - содержит только неповторяющиеся символы.

Вы можете построить эти два Set s в одном l oop. После этого l oop вы возвращаете первый Character в uniques Set. Я использовал LinkedHashSet для uniques, чтобы вы получили первый неповторяющийся символ (это первый символ, добавленный к этому Set, который не был впоследствии удален).

Set<Character> all = new HashSet<>(); 
Set<Character> uniques = new LinkedHashSet<>();
for(int i=0; i<string.length(); i++) { 
    char c = string.charAt(i); 
    if (all.add(c)) { // returns true if this is the first time c appears in the String
        uniques.add(c); 
    } else { // c already appeared in the String
        uniques.remove(c);
    } 
} 
return uniques.isEmpty () ? ' ' : uniques.iterator().next();
2 голосов
/ 06 февраля 2020

Создайте карту частот, используя LinkedHashMap<Character, Integer>, затем итерируйте карту, пока не найдете первую с частотным счетом 1. Вы должны использовать LinkedHashMap, чтобы при наличии более одного неповторяющегося символа , они будут на карте в том же порядке, что и во входной строке. Построение карты - O (n) (амортизировано), а поиск неповторяющегося символа - O (n) , поэтому общая сложность составляет O (n) .

Еще лучше, используйте Streams для построения LinkedHashMap<Integer, Long>, где ключом является кодовая точка Unicode. Таким образом, ваше решение может обрабатывать персонажей из дополнительных плоскостей, таких как Emojis. 101

import static java.util.function.Function.identity;
import static java.util.stream.Collectors.counting;
import static java.util.stream.Collectors.groupingBy;
import java.util.LinkedHashMap;
static String firstNonRepeatingCharacter(String text) {
    return text.codePoints().boxed()
        .collect(groupingBy(identity(), LinkedHashMap::new, counting()))
        .entrySet().stream()
        .filter(e -> e.getValue() == 1)
        .findFirst()
        .map(e -> Character.toString(e.getKey()))
        .orElse("");
}

Приведенный выше код требует Java 11+. Для Java 8+ используйте:

        .map(e -> new String(new int[] { e.getKey() }, 0, 1))

Тест

System.out.println(firstNonRepeatingCharacter("aabefddbccffaa"));
System.out.println(firstNonRepeatingCharacter("aabefddbccffaae"));
System.out.println(firstNonRepeatingCharacter("aabefddbccffaae?"));

Выход

e

?
...