top k频繁元素-如何反转元素

bksxznpy 于 2021-07-06 发布在 Java

关注(0)|答案(2)|浏览(408)

我在下面附上了一张问题的图片，可以更详细地解释这个问题。我们的目标是找到单词词典中出现次数最多的k个单词。我的方法是在hashmap中获取频率，然后使用优先级队列来存储max k元素。然后我将max k元素添加到我的返回列表中并返回它。
对于图片中给定的输入，我的代码返回正确的输出-[“i”，“love”]。问题是输入如下：

input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"]
output: ["day","sunny","is","the"]
expected: ["the","is","sunny","day"]

正确的答案应该是当前字符串的反转，但是如果我在返回原始输入（图片中的输入）之前反转字符串，则不再工作。
我认为这与值在频率相同的情况下如何存储在优先级队列中有关…但我不确定是否要检查这一点。
有没有想过我该怎么解决这个问题？

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
       HashMap<String, Integer> map = new HashMap<>();
       List<String> mostFrequent = new ArrayList<>();

        for(int i = 0; i < words.length; i++) {
            if(map.containsKey(words[i])) {
                map.put(words[i], map.get(words[i]) + 1);
            }
            else {
                map.put(words[i], 1);
            }
        }

        PriorityQueue<String> pq = new PriorityQueue<String>((a,b) -> map.get(a) - map.get(b));

        for(String s : map.keySet()) {
            pq.add(s);
            if(pq.size() > k) {
                pq.remove();
            }
        }

        for(String s : pq) {
            mostFrequent.add(s);
        }

        //Collections.reverse(mostFrequent);

        return mostFrequent;
    }
}

Java heap priority-queue word-frequency

来源：https://stackoverflow.com/questions/65032354/top-k-frequent-elements-how-to-reverse-elements

2条答案

按热度按时间

mwecs4sa1#

一种方法是通过如下方式更改代码，

class Solution {
    public static List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        List<String> mostFrequent = new ArrayList<>();

        for(int i = 0; i < words.length; i++) {
            if(map.containsKey(words[i])) {
                map.put(words[i], map.get(words[i]) + 1);
            }
            else {
                map.put(words[i], 1);
            }
        }

//Below I am sorting map based on asked condition and storing it into the list.
        List<Map.Entry<String,Integer>> sorted = new ArrayList<>(map.entrySet());
        Collections.sort(sorted,(Map.Entry<String,Integer> x,Map.Entry<String,Integer> y) -> x.getValue().compareTo(y.getValue()) == 0? x.getKey().compareTo(y.getKey()):x.getValue().compareTo(y.getValue()) > 0 ? -1 : 1 );

        for(Map.Entry<String,Integer> e : sorted) {
            mostFrequent.add(e.getKey());
        }

        return mostFrequent;
    }

在这里，创建频率图后，我将根据频率对它们进行排序，并创建一个新的频率图 ArrayList .

赞(0）回复(0）举报 2021-07-06

kx1ctssn2#

你差点就成功了。但是你有一些虫子。
起初，您的解决方案不完整。在最初的任务中，他们不仅询问了频率，还询问了频率是否相等的附加问题——按字母顺序输出元素。为了实现这一点，您可以将以下比较器用于priorityqueue：

PriorityQueue<String> pq = new PriorityQueue<String>((a, b) -> {
    int countComparison = Integer.compare(map.get(a), map.get(b));
    if (countComparison == 0)
        return b.compareTo(a);
    return countComparison;
});

而且，解决方案的下一个错误是迭代priorityqueue。priorityqueue迭代器不保证任何特定顺序。来自javadocs
方法iterator（）中提供的迭代器不能保证以任何特定顺序遍历优先级队列的元素。
因此，您需要轮询队列中的元素。以及责任方：

while(!pq.isEmpty()) {
   String s = pq.poll();
   mostFrequent.add(s);
}

最后一部分-由于队列中元素的顺序（从最低到最高），您需要反转输出数组：

Collections.reverse(mostFrequent);

最终解决方案如下：

public List<String> topKFrequent(String[] words, int k) {
    HashMap<String, Integer> map = new HashMap<>();
    List<String> mostFrequent = new ArrayList<>();

    for(int i = 0; i < words.length; i++) {
        if(map.containsKey(words[i])) {
            map.put(words[i], map.get(words[i]) + 1);
        }
        else {
            map.put(words[i], 1);
        }
    }

    PriorityQueue<String> pq = new PriorityQueue<String>((a, b) -> {
        int countComparison = Integer.compare(map.get(a), map.get(b));
        if (countComparison == 0)
            return b.compareTo(a);
        return countComparison;
    });

    for(String s : map.keySet()) {
        pq.add(s);
        if(pq.size() > k) {
            pq.remove();
        }
    }

    while(!pq.isEmpty()) {
        String s = pq.poll();
        mostFrequent.add(s);
    }
    Collections.reverse(mostFrequent);

    return mostFrequent;
}

赞(0）回复(0）举报 2021-07-06

我来回答

top k频繁元素-如何反转元素

2条答案

相关问题

热门标签

最新问答