0

我需要根据其频率对单词列表进行排序。

我的输入：

Haha, hehe, haha, haha, hehe, hehe.... , Test

例如在我的数据结构中，我会有

Haha:3
Hehe:5
Test:10

我需要以这种方式在输出中对数据结构进行排序：

Test:10
Hehe:5
Haha:3

这样，如果我弹出数据结构的顶部，我将能够获得元素及其相应的频率。

元素的数量最初是未知的，因此数组是不可行的。如果我想获得前几个元素，我只需要按顺序访问它。这在Java中可能吗？

4

3 回答 3

2

首先，要确认：你能在排序前得到所有的单词吗？还是这些词源源不断地涌来？

(1)对于前一种情况，你可以使用 aSet来存储单词，然后将它们放入 aPriorityQueue中。如果你实现了比较器功能，队列会自动对单词进行排序。我创建了一个新类Pair来存储文本和频率，请参见代码：

import java.util.Queue;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.HashSet;
import java.util.Comparator;

public class PriorityQueueTest {

    public static class Pair {
        private String text;
        private int frequency;

        @Override
        public int hashCode() {
            return text.hashCode();
        }

        @Override
        public String toString() {
            return text + ":" + frequency;
        }

        public Pair(String text, int frequency) {
            super();
            this.text = text;
            this.frequency = frequency;
        }

        public String getText() {
            return text;
        }
        public void setText(String text) {
            this.text = text;
        }
        public int getFrequency() {
            return frequency;
        }
        public void setFrequency(int frequency) {
            this.frequency = frequency;
        }
    }

    public static Comparator<Pair> idComparator = new Comparator<Pair>(){
        @Override
        public int compare(Pair o1, Pair o2) {
            if(o1.getFrequency() > o2.getFrequency()) {
                return -1;
            }
            else if(o1.getFrequency() < o2.getFrequency()){
                return 1;
            }
            else {
                return 0;
            }
        }
    };

    public static void main(String[] args) {
        Set<Pair> data = new HashSet<Pair>();
        data.add(new Pair("haha", 3));
        data.add(new Pair("Hehe", 5));
        data.add(new Pair("Test", 10));

        Queue<Pair> queue = new PriorityQueue(16, idComparator);

        for(Pair pair : data) {
            queue.add(pair);
        }

        // Test the order
        Pair temp = null;
        while((temp = queue.poll()) != null) {
            System.out.println(temp);
        }

    }

}

(2)对于其他情况（单词连续出现），您可以使用aTreeMap来保持顺序。见参考：http ://www.java-samples.com/showtutorial.php?tutorialid=370

于 2014-03-22T04:45:47.777 回答
1
  1. 项目清单

我从下面的 URL 作为参考开始，我将在该参考的基础上进行构建：

如何计算 Python 中列表项的出现次数？

现在，建筑开始了：

>>> from collections import Counter
>>> word_list = ['blue', 'red', 'blue', 'yellow', 'blue', 'red','white','white']
>>> Counter(word_list)
Counter({'blue': 3, 'red': 2, 'white': 2, 'yellow': 1})

请注意 Counter(word_list) 如何显示元素列表，即按频率降序排列的单词/频率对。不幸的是，提取单词并将它们编译到按相同顺序排序的列表中需要更多的工作：

(1) 获取“大小”作为 JSON 对象中的元素个数。

(2) 对 JSON 对象应用“most_common”方法，以获取按频率排序的元素数组。

(3) 应用列表推导生成从排序数组中提取的单词列表。

>>> size = len(Counter(word_list))
4
>>> word_frequency_pairs = Counter(word_list).most_common(size)
>>> word_frequency_pairs
[('blue', 3), ('white', 2), ('red', 2), ('yellow', 1)]
>>> [i[0] for i in word_frequency_pairs]
['blue', 'white', 'red', 'yellow']

我喜欢 Python 是有原因的 :)

于 2014-03-22T04:56:50.993 回答
1

为了保留您需要的信息，您可以创建一个包含您的字符串和计数（例如Pair）的类，并将此类的实例保存在List<Pair>. 这种方法会使给定字符串的计数增加效率低下，因为您必须在线性时间（O(N)）中查找保存字符串的元素，然后增加它。

更好的方法是使用 a Map<String, Integer>，这样搜索是在恒定时间 ( O(1) ) 内完成的，然后您可以对Set<Map.Entry<String, Integer>>返回的元素进行排序Map.entrySet()。

于 2014-03-22T03:37:39.957 回答