数组中第 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类而不是其他数据结构如字典或哈希表来计数?
▷🦆
解题思路中提到遍历Counter的键来寻找独一无二的字符串,是否有考虑到Counter可能不会按照arr中字符串的原始顺序排序?这如何影响寻找第k个独一无二字符串的逻辑?
▷🦆
题解中提到,如果遍历结束后没有找到足够的独一无二字符串,函数返回空字符串。能否详细说明是在什么情况下会出现这种情况?
▷🦆
在算法中,如果arr数组非常大或者k的值非常大但独一无二的字符串数量很少,这种情况下算法的表现如何?能否优化?
▷