如何在文本文件中查找N个最长的行

Question

编写一个程序来读取多行文本文件，并将最长的N行写入标准输出。

还有一个类似的问题，但我并不真正理解它，因为它涉及到使用min-heap，这将增加更多的工作，因为我必须创建一个min-heap数据结构。

我尝试创建一个大小为n的数组，然后对其进行排序，但每次在数组中插入新行时，我都必须对其进行排序。我想知道最简单的方法是什么，最优的方法是什么。

Answer 1

创建一个包含N个字符串的数组。

循环遍历文件。

如果数组中的项数

在所有情况下，将行的最短长度存储在数组中。如果数组已满，则与最短的行进行比较，如果新行是>，则替换该行，并找到最短的行。

重复循环。

打印字符串。

Answer 2

编辑：正如其他人提到的，我的第一个解决方案不适用于相同长度的行。更好的方法是使用java.util.PriorityQueue<Line>并定义对象线，如下所示：

class Line {
  private final String line;
  public Line(String line) {
    this.line = line;
  }

  public int getLen() {
    return line.length();
  }

  public String getLine() {
    return line;
  }
} 

然后实例化一个PriorityQueue并使用Comparator指定顺序。

PriorityQueue：PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

创建一个具有指定初始容量的PriorityQueue，它根据指定的比较器对其元素进行排序。

这是一个使用单元测试的实验。

        int n = 1;
        PriorityQueue<Line> queue = new PriorityQueue<Line>(n, new Comparator<Line>() {
            @Override
            public int compare(Line a, Line b) {
                return a.getLen() - b.getLen();
            }
        });

        queue.add(new Line("abcd"));
        queue.add(new Line("abcde"));
        queue.add(new Line("abc"));

        assertEquals(queue.poll().getLine(), "abc");
        assertEquals(queue.poll().getLine(), "abcd");
        assertEquals(queue.poll().getLine(), "abcde");

在本例中，我们看到轮询删除首先删除列表中最小元素。您可以简单地在每次插入行后调用queue.poll() if queue.size() > n。

Answer 3

以下是我的解决方案

使用树地图的原因是为了处理多个长度相同的行，在这种情况下，所有行都将被添加到同一个ArrayList中

public class DataCollector {

    private int size;
    private TreeMap<Integer, List<String>> data = new TreeMap<Integer, List<String>>();

    public DataCollector(int nthLargest) {

        if (nthLargest < 1) {
            throw new IllegalArgumentException("can not be smaller than 1");
        }

        this.size = nthLargest;
    }

    public void feed(String line) {

        int length = line.length();

        if (data.size() > 0 && length < data.firstKey()) {
            return;
        }

        getList(length).add(line);



        if (data.size() > size) {
            data.remove(data.firstKey());
        }
    }

    private List<String> getList(int key) {
        if (!data.containsKey(key)) {
            data.put(key, new ArrayList<String>());
        }

        return data.get(key);
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();

        for (Entry<Integer, List<String>> entry : data.entrySet()) {
            builder.append(entry.getKey()).append("=").append(entry.getValue()).append("\r\n");
        }

        return builder.toString();
    }

    public List<String> getResult() {


        if (data.isEmpty()) {
            return Collections.EMPTY_LIST;
        }

        return data.firstEntry().getValue();
    }
    public static void main(String[] args) {

        DataCollector co = new DataCollector(1);


        co.feed("b");
        co.feed("abc");
        co.feed("abc1");
        co.feed("abc2");
        co.feed("abc33");
        co.feed("abc34");
        co.feed("abc23");
        co.feed("abc23b");
        co.feed("abc23b");
        co.feed("abc23c");
        co.feed("abc23dd");
        co.feed("abc23ee");
        co.feed("a");

        System.out.println(co);
        System.out.println(co.getResult());

    }

}