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

难度: Easy

独一无二的字符串 指的是在一个数组中只出现过一次的字符串。

给你一个字符串数组 arr 和一个整数 k ，请你返回 arr 中第 k 个 独一无二的字符串 。如果少于 k 个独一无二的字符串，那么返回 空字符串 "" 。

注意，按照字符串在原数组中的顺序找到第 k 个独一无二字符串。

示例 1:

输入：arr = ["d","b","c","b","c","a"], k = 2
输出："a"
解释：
arr 中独一无二字符串包括 "d" 和 "a" 。
"d" 首先出现，所以它是第 1 个独一无二字符串。
"a" 第二个出现，所以它是 2 个独一无二字符串。
由于 k == 2 ，返回 "a" 。

示例 2:

输入：arr = ["aaa","aa","a"], k = 1
输出："aaa"
解释：
arr 中所有字符串都是独一无二的，所以返回第 1 个字符串 "aaa" 。

示例 3：

输入：arr = ["a","b","a"], k = 3
输出：""
解释：
唯一一个独一无二字符串是 "b" 。由于少于 3 个独一无二字符串，我们返回空字符串 "" 。

提示：

1 <= k <= arr.length <= 1000
1 <= arr[i].length <= 5
arr[i] 只包含小写英文字母。

Submission

运行时间: 26 ms

内存: 16.2 MB

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        cnt = Counter(arr)
        t = 0
        for c in cnt:
            if cnt[c] == 1:
                t += 1
                if t == k:
                    return c
        else:
            return ""

Explain

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

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        cnt = Counter(arr)  # 使用Counter统计每个字符串的出现次数
        t = 0  # 初始化独一无二字符串的计数器
        for c in cnt:  # 遍历计数器中的每个字符串
            if cnt[c] == 1:  # 如果该字符串独一无二
                t += 1  # 更新独一无二字符串的计数器
                if t == k:  # 如果找到了第k个独一无二的字符串
                    return c  # 返回该字符串
        else:
            return ""  # 如果没有足够的独一无二字符串，返回空字符串

Explore

在Python中，Counter类是collections模块下专门为计数设计的一个子类，它继承自字典（dict）。使用Counter类的主要优势是它自动处理不存在的键的情况，即当尝试计数一个新元素时，不需要额外的代码来检查键是否存在字典中。此外，Counter提供了额外的实用方法，如most_common，这些方法可以方便地实现一些常见的统计任务。虽然使用普通字典也可以达到同样的效果，但使用Counter可以使代码更简洁、易读，且减少出错的可能。

实际上，Counter类的实现保持插入顺序，这是Python 3.7及以上版本的dict类所具有的特性。因此，当使用Counter对元素进行计数时，遍历Counter对象实际上是按照元素首次出现的顺序进行的。这意味着即使在计数时使用Counter，也能保持数组arr中字符串的原始出现顺序，从而精确地找到第k个独一无二的字符串。

如果在遍历结束后没有找到足够的独一无二字符串，返回空字符串的情况通常发生在两种情况下：一是数组arr中的独一无二的字符串数量少于k个；二是数组arr为空。在这些情况下，即使遍历了整个数组也无法找到第k个独一无二的字符串，因此按照题目要求，返回一个空字符串表示没有找到符合条件的结果。

如果arr数组非常大，Counter类的使用将导致较高的内存消耗，因为需要存储每个元素及其出现的次数。如果k值非常大而独一无二的字符串很少，算法将遍历整个计数器而可能找不到结果，从而导致时间浪费。为优化这种情况，可以考虑首先检查独一无二的字符串数量，如果数量少于k，则直接返回空字符串，避免不必要的遍历。此外，还可以使用更高效的数据结构如哈希表来手动管理计数，避免使用Counter可能带来的额外开销。