#java #python #c #string #algorithm
#java #python #c #строка #алгоритм
Вопрос:
Там приведен список строк, из которых мы должны распечатать уникальные строки. Уникальная строка — это строка, которая не повторяется в списке строк.
Ex li = [ram,raj,ram,dev,dev]
unique string = raj.
Я подумал об одном алгоритме.
Сначала отсортируйте массив строк, затем проверьте соседнюю строку, если она равна, затем переместитесь вперед, иначе это уникальная строка. Но здесь очень высока временная сложность для сортировки массива строк.
Может ли какой-либо орган помочь мне найти более эффективный алгоритм, чем мой алгоритм? Заранее спасибо.
Комментарии:
1. Создайте счетчик частоты (который может быть просто хэш-картой) для подсчета количества вхождений каждой строки (линейное время). Затем распечатайте только те строки, которые имеют количество одноэлементных элементов (линейное время)
2. спасибо @inspectorG4dget. Я понял.
3. Начните с выбора языка.
4. @shmosel Я использую Java для кодирования. Я также отметил python и c в вопросе, потому что я хотел знать эффективный алгоритм, а не код. Если я получу эффективный алгоритм, я смогу кодировать на любом языке. Кроме того, этот вопрос также будет опубликован в сообществе python и c , и я могу получить лучшее решение от разных программистов. И основные конкурентоспособные программисты делают кодирование на c .
Ответ №1:
Решение 1
Вы можете решить свою проблему в O (n) сложности.
просто создайте хэш-таблицу для хранения счетчиков слов, а затем получите доступ только к словам с помощью count == 1
Решение 2
Это решение не является линейным по времени, но все же было хорошим.
Вы можете создать Trie со свойством count, поэтому будет легко найти узлы с помощью count == 1
Ответ №2:
Вы могли бы попробовать ниже
List<String> names = Arrays.asList("ram", "raj", "ram", "dev", "dev");
Map<String, Long> nameCount = names.stream().collect(Collectors.groupingBy(s -> s, Collectors.counting()));
List<String> unique = nameCount.entrySet().stream().filter(e -> e.getValue() == 1L).map(Map.Entry::getKey).collect(Collectors.toList());
System.out.println(nameCount);
System.out.println(unique);
вывод
{dev=2, raj=1, ram=2}
[raj]
Редактировать
List<String> uniq = new ArrayList<>();
names.stream().sorted().forEach(n -> {
if (uniq.contains(n)) {
uniq.remove(n);
} else {
uniq.add(n);
}
});
Вместо списка map можно использовать cab для проверки contains в O(1)
Ответ №3:
Вы можете попробовать эту простую реализацию на python, которая основана на концепции использования хэш-карты:
li = ['ram','raj','ram','dev','dev']
hash = dict()
for item in li:
if item in hash:
hash[item] = 1
else:
hash[item] = 1
print "unique string(s):",
for key, value in hash.iteritems():
if value == 1:
print key,