leetcode
leetcode 1801 ~ 1850
数组中第 K 个独一无二的字符串

数组中第 K 个独一无二的字符串

难度:

标签:

题目描述

代码结果

运行时间: 26 ms, 内存: 16.2 MB


/*
题目思路:
1. 使用 Java Stream 统计每个字符串的出现次数。
2. 过滤出出现次数为 1 的字符串。
3. 找到第 k 个独一无二的字符串。如果数量不足 k,返回空字符串。 */

import java.util.*;
import java.util.stream.*;

public class UniqueStringFinderStream {
    public String kthUniqueString(String[] arr, int k) {
        Map<String, Long> frequencyMap = Arrays.stream(arr)
                .collect(Collectors.groupingBy(s -> s, LinkedHashMap::new, Collectors.counting()));
        List<String> uniqueStrings = frequencyMap.entrySet().stream()
                .filter(entry -> entry.getValue() == 1)
                .map(Map.Entry::getKey)
                .collect(Collectors.toList());
        return k <= uniqueStrings.size() ? uniqueStrings.get(k - 1) : "";
    }
}

解释

方法:

解题思路首先是使用Counter类从collections库来计数数组中每个字符串出现的次数。随后,遍历计数器的键,即字符串,检查其对应的计数值。如果计数值为1,说明该字符串在数组中仅出现一次,是独一无二的。通过一个计数器t来记录找到的独一无二字符串数量,当t达到k时,返回当前字符串。如果遍历结束后没有找到足够的独一无二字符串,函数最后返回一个空字符串。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在解题过程中,为什么选择使用Counter类而不是其他数据结构如字典或哈希表来计数?
在Python中,Counter类是collections模块下专门为计数设计的一个子类,它继承自字典(dict)。使用Counter类的主要优势是它自动处理不存在的键的情况,即当尝试计数一个新元素时,不需要额外的代码来检查键是否存在字典中。此外,Counter提供了额外的实用方法,如most_common,这些方法可以方便地实现一些常见的统计任务。虽然使用普通字典也可以达到同样的效果,但使用Counter可以使代码更简洁、易读,且减少出错的可能。
🦆
解题思路中提到遍历Counter的键来寻找独一无二的字符串,是否有考虑到Counter可能不会按照arr中字符串的原始顺序排序?这如何影响寻找第k个独一无二字符串的逻辑?
实际上,Counter类的实现保持插入顺序,这是Python 3.7及以上版本的dict类所具有的特性。因此,当使用Counter对元素进行计数时,遍历Counter对象实际上是按照元素首次出现的顺序进行的。这意味着即使在计数时使用Counter,也能保持数组arr中字符串的原始出现顺序,从而精确地找到第k个独一无二的字符串。
🦆
题解中提到,如果遍历结束后没有找到足够的独一无二字符串,函数返回空字符串。能否详细说明是在什么情况下会出现这种情况?
如果在遍历结束后没有找到足够的独一无二字符串,返回空字符串的情况通常发生在两种情况下:一是数组arr中的独一无二的字符串数量少于k个;二是数组arr为空。在这些情况下,即使遍历了整个数组也无法找到第k个独一无二的字符串,因此按照题目要求,返回一个空字符串表示没有找到符合条件的结果。
🦆
在算法中,如果arr数组非常大或者k的值非常大但独一无二的字符串数量很少,这种情况下算法的表现如何?能否优化?
如果arr数组非常大,Counter类的使用将导致较高的内存消耗,因为需要存储每个元素及其出现的次数。如果k值非常大而独一无二的字符串很少,算法将遍历整个计数器而可能找不到结果,从而导致时间浪费。为优化这种情况,可以考虑首先检查独一无二的字符串数量,如果数量少于k,则直接返回空字符串,避免不必要的遍历。此外,还可以使用更高效的数据结构如哈希表来手动管理计数,避免使用Counter可能带来的额外开销。

相关问题