2.5.8

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

官网实现见:https://algs4.cs.princeton.edu/25applications/Frequency.java.html
用到的数据来自(右键另存为):https://introcs.cs.princeton.edu/java/data/tale.txt

先把所有单词读入,然后排序,一样的单词会被放在一起,
接下来遍历一遍记录每个单词出现的次数。
然后按照频率排序,倒序输出即可。

定义了一个嵌套类 Record 来记录单词及出现次数,实现的比较器按照出现次数排序。

class Record : IComparable<Record>
{
    public string Key { get; set; }     // 单词
    public int Value { get; set; }      // 频率

    public Record(string key, int value)
    {
        this.Key = key;
        this.Value = value;
    }

    public int CompareTo(Record other)
    {
        return this.Value.CompareTo(other.Value);
    }
}

测试结果(前 1% 的单词):

代码

using System;
using System.IO;

namespace _2._5._8
{
    class Program
    {
        class Record : IComparable<Record>
        {
            public string Key { get; set; }     // 单词
            public int Value { get; set; }      // 频率

            public Record(string key, int value)
            {
                this.Key = key;
                this.Value = value;
            }

            public int CompareTo(Record other)
            {
                return this.Value.CompareTo(other.Value);
            }
        }

        static void Main(string[] args)
        {
            string filename = "tale.txt";
            StreamReader sr = new StreamReader(File.OpenRead(filename));
            string[] a = sr.ReadToEnd().Split(new char[] { ' ', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);
            Array.Sort(a);

            Record[] records = new Record[a.Length];
            string word = a[0];
            int freq = 1;
            int m = 0;
            for (int i = 0; i < a.Length; i++)
            {
                if (!a[i].Equals(word))
                {
                    records[m++] = new Record(word, freq);
                    word = a[i];
                    freq = 0;
                }
                freq++;
            }
            records[m++] = new Record(word, freq);

            Array.Sort(records, 0, m);
            // 只显示频率为前 1% 的单词
            for (int i = m - 1; i >= m * 0.99; i--)
                Console.WriteLine(records[i].Value + " " + records[i].Key);
        }
    }
}
上一题 下一题