0

Стоит задача, получить из строки только уникальные элементы, все дублируещиеся элементы необходимо удалить. Пример:

Input:
String line = "Однажды в стране и однажды в мире";
Output:
"стране и мире"

Во первых я получаю массив слов

String[] words = str.replaceAll("[^\\da-zA-Za-яёА-ЯЁ ]", "").toLowerCase().split(" ");

Затем мне надо пройти по этому массиву и сравнить первый элемент с последующими и если нахожу повтор, то беру следующий элемент и если он не повторяется, то ложу его в список List<String> uniqueWords = new ArrayList<>() Написал так:

for (int i = 0; i < words.length; i++) {
    String temp = words[i];
    for (int j = 0; j < uniqueWords.size(); j++) {
        if (uniqueWords.get(j).equals(temp)){
            break;
        } else {
             uniqueWords.add(temp);
           }
      }
  }

for(String cell : uniqueWords){
    result.append(cell).append(" ");
 }
System.out.println(result);

Но это не работает. Что-то упускаю и делаю не правильно, а разобраться не могу.Хотелось бы сделать это без использования Map Прошу помощи в данном вопросе.

3 ответа 3

2

Такая задача стандартно решается построением мапы частот слов Map<String, Integer> и последующей фильтрацией по частоте слова, не превышающей 1. Это позволяет решить её без квадратичного поиска, со сложностью O(N).

Кроме того, для получения массива слов излишним будет применение replaceAll, достаточно будет разбить строку по символам, не являющимся буквами или цифрами [^\p{L}\p{N}]

String[] words = str.toLowerCase().split("[^\\p{L}\\p{N}]+");

Для построения мапы удобно использовать Stream API:

List<String> uniqueWords = Arrays.stream(words)
    .collect(Collectors.groupingBy(
        w -> w, LinkedHashMap::new, Collectors.counting()
    )) // Map<String, Long>
    .entrySet()
    .stream() // Stream<Map.Entry<String, Long>>
    .filter(e -> 1L == e.getValue())
    .map(Map.Entry::getKey)
    .collect(Collectors.toList());
System.out.println(uniqueWords);
System.out.println(String.join(" ", uniqueWords));

Вывод:

[стране, и, мире]
стране и мире

Без применения мап и вычисления частоты можно использовать два Set -- первый будет регистрировать все вхождения, а второй -- только дубликаты, используя факт, что метод Set::add возвращает false, если элемент уже существует в данном сете, после завершения основного цикла из первого сета следует удалить все обнаруженные дубликаты при помощи Set::removeAll.

Здесь также будет сложность O(N).

Set<String> uniques = new LinkedHashSet<>();
Set<String> dups = new HashSet<>();
for (String word : words) {
    if (!uniques.add(word)) {
        dups.add(word);
    }
}
uniques.removeAll(dups);
System.out.println(uniques);
System.out.println(String.join(" ", uniques));

Вывод:

[стране, и, мире]
стране и мире

Использовав Set<String> uniques = new TreeSet<>(); можно отсортировать слова по алфавиту.


Также можно несколько оптимизировать существующее решение, если устанавливать слова-дубликаты в null при итерации по массиву words, в лучшем случае (все дубликаты) будет сложность O(N), в худшем (ни одного дубликата) квадратичная сложность сохранится, но реально количество итераций составит n * (n - 1) / 2:

for (int i = 0, n = words.length; i < n; i++) {
    String word = words[i];
    if (null == word) {
        continue; // обнаружен удалённый дубликат
    }
    boolean unique = true;
    for (int j = i + 1; j < n; j++) {
        if (word.equals(words[j])) {
            unique = false;
            words[j] = null;
        }
    }
    if (unique) {
        uniqueWords.add(word);
    }
}
System.out.println(uniqueWords);
2
  • Alex Rudenko, Это уже высший пилотаж ))) Спасибо, буду углубляться в изучение коллекций и стримов
    – YuriiS
    10 дек 2021 в 17:40
  • Alex Rudenko, отличная логика, как я не додумался до такого ... метод add возвращает false если слово не помещается в Set, значит оно дубликат и его надо положить в список дубликатов, а потом просто вывести этот список в консоль. Супер. Как научиться находить разные варианты решения ??
    – YuriiS
    10 дек 2021 в 18:00
1

Вы сразу кладёте слово, если первая же проверка удаётся, а нужно выждать до конца. И сравнивать не с отобранными уникальными, а с остатком массива.(Флаг сделайте булевским, как там оно у вас в Java записывается)

for (int i = 0; i < words.length; i++) {
    String temp = words[i];
    int flag = 1;  
    for (int j = 0; j < words.length; j++) {
        if ((i!=j) && (words.get(j).equals(temp))){
            flag = 0;
            break;
        }
      }
   if (flag==1) {
       uniqueWords.add(temp);
   }
  }
1
  • Отметил ответ MBo так, как он был первым. Спасибо за подсказку, я действительно не учитывал, что надо идти до конца и сравнивать с остатком массива.
    – YuriiS
    10 дек 2021 в 9:55
1

Исходя из Вашего ТЗ, могу предложить Вам следующий код

        String line = "Однажды в стране и однажды в мире";
        String[] words = line.replaceAll("[^\\da-zA-Za-яёА-ЯЁ ]", "").toLowerCase().split(" ");
        List<String> wordList = new ArrayList<>();
        for (String word : words) {
            int count = 0;
            for (String s : words) {
                if (word.equalsIgnoreCase(s))
                    count++;
            }
            if (count == 1)
                wordList.add(word);
        }
        System.out.println(wordList);
3
  • Ваш ответ тоже очень полезен, но я уже отметил верное решение. А word.equalsIgnoreCase(s) можно не делать, я же уже перевел все символы в нижний регистр
    – YuriiS
    10 дек 2021 в 9:57
  • @YuriiS Решение помечается галочкой, а плюсики можно хоть всем ставить.
    – MBo
    10 дек 2021 в 10:01
  • MBo, поставил ))
    – YuriiS
    10 дек 2021 в 10:09

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.