根据值在Map<String，Double>中获取前N个元素的最佳方法是什么？
根据值在Map<String，Double>中获取前N个元素的最佳方法是什么？
提问于 2018-09-04 13:35:31
例如，如果我有一个由{"A", 0.0}, {"B", 3.14}, {"C", 3.14}, {"D", 8.8}, {"E", 2.1}, {"F", 1.01}组成的映射，并且前3个关键字将是{"D", "B", "C"}。
我知道做这件事的程序化方法，但是在Java8中有没有更智能的/函数式的方法呢？
编辑:请注意，我们可以将映射的每个元素放入大小为N的优先级队列中，因此时间复杂度应该是M_log(N)，比排序所有M个元素的M_log(M)更快。
编辑2:按照要求，这是我得到的：
public static void main(String args[]) {
final Map<String, Double> map = new HashMap<String, Double>() {{
put("A", 0.0);
put("B", 3.14);
put("C", 3.14);
put("D", 8.8);
put("E", 2.1);
put("F", 1.01);
}};
System.out.println("answer= " + getTopN(map, 3).toString());
}
static List<String> getTopN(final Map<String, Double> map, int n) {
// Creating priority queue with limit size n
PriorityQueue<Entry<String, Double>> pq = new PriorityQueue<>(n, Entry.comparingByValue());
for (Entry<String, Double> entry : map.entrySet()) {
pq.add(entry);
if (pq.size() > n) {
pq.poll();
}
}
Stack<String> stack = new Stack<>();
while (!pq.isEmpty()) {
stack.add(pq.poll().getKey());
}
final ArrayList<String> answer = new ArrayList<>();
while (!stack.isEmpty() && n-- > 0) {
answer.add(stack.pop());
}
return answer;
}回答 2
Stack Overflow用户
回答已采纳
发布于 2018-09-06 03:05:34
可以通过使用TreeSet (而不是PriorityQueue和Stack)来改进您的代码：
static List<String> getTopN(Map<String, Double> map, int n) {
TreeSet<Map.Entry<String, Double>> topN = new TreeSet<>(
Map.Entry.<String, Double>comparingByValue()
.reversed() // by value descending, then by key
.thenComparing(Map.Entry::getKey)); // to allow entries with repeated values
map.entrySet().forEach(e -> {
topN.add(e);
if (topN.size() > n) topN.pollLast();
});
return topN.stream()
.map(Map.Entry::getKey)
.collect(Collectors.toList());
}这是为了使集合能够包含具有相等值的项目。
Stack Overflow用户
发布于 2018-09-04 13:51:41
下面是一种通过条目值使用反向双重比较器的方法：
Map<String, Double> map = new HashMap<>();
map.put("A", 0.0);
map.put("B", 3.14);
map.put("C", 3.14);
map.put("D", 8.8);
map.put("E", 2.1);
map.put("F", 1.01);
List<String> topKeys = map.entrySet().stream()
.sorted(Comparator.<Entry<String, Double>>comparingDouble(Entry::getValue)
.reversed())
.limit(3) //limit to 3
.map(Entry::getKey)
.collect(Collectors.toList());返回的列表包含[D, B, C]
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52159397
复制相关文章
相似问题