主页 / 问题 / 1359329
Accepted
YuriiS
Asked:2022-05-10 16:48:18 +0000 UTC2022-05-10 16:48:18 +0000 UTC

仅从字符串中获取唯一元素

  • 772

任务是从字符串中仅获取唯一元素，必须删除所有重复元素。例子：

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 I ask for help in this matter 的情况下做到这一点。

java

3 个回答

  1. 此类问题通常通过构建词频图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- 第一个将记录所有出现，第二个 - 仅重复，如果元素已经存在于该集合中，则该方法在 main 完成后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
  2. Best Answer

    如果第一次检查成功，您立即输入单词，但您需要等到最后。并且不与选定的唯一值进行比较，而是与数组的其余部分进行比较。（将标志设为布尔值，因为它是用 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

  3. 根据您的 TK，我可以为您提供以下代码

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

相关问题