Получить из строки только уникальные элементы

Question

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

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 Прошу помощи в данном вопросе.

Answer 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);
   }
  }

Answer 2

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

        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);

Answer 3

Такая задача стандартно решается построением мапы частот слов 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);

БЛОГ НА HUSL

Получить из строки только уникальные элементы

Ответы (3 шт):