2018-04-27 海量数字中找到最大/小的K个（TopK 问

来自xie4ever
假如业务场景需要在十亿个数字中找到最小k个的数字。设计算法。

1. 排序方法。最容易想到肯定是排序了。纵观所有的排序方法，即使是相对较快的快速排序也是 O(nlogn) 的时间复杂度。而且快速排序是内排序，将海量数据一次性加载到内存里面，内存容量可能无法承受，所以该方法适合的数据规模十分有限 。
2. 双向链表。构建含有 k 个元素的双向链表，然后

import java.util.Random;
public class TestEliminate {
    static Random random = new Random();

    static class Node {

        int value;
        Node next;
        Node pre;

        public Node(int value) {

            this.value = value;
        }
    }

    static class Result {

        Node head;
        Node tail;
        int length;

        public Result(int length) {

            this.length = length;

            this.head = new Node(Integer.MAX_VALUE);

            this.tail = new Node(Integer.MAX_VALUE);

            Node temp = head;

            for (; length > 2; length--) { // 元素太少（只有头尾的情况），不需要考虑中间节点，直接连接头尾节点即可

                Node t = new Node(Integer.MAX_VALUE);

                temp.next = t;

                t.pre = temp;

                temp = t;
            }

            temp.next = tail; // 连接节点，形成双链表

            tail.pre = temp;
        }
    }

    public static void main(String[] args) {

        Result result = new Result(10);

        long start = System.currentTimeMillis();

        for (int i = 0; i < 1000000000; i++) {

            int tempNum = random.nextInt(Integer.MAX_VALUE); // 提供100000000个随机数

            if (tempNum < result.head.value) { // 如果此数比头结点还小，那么就成为新的头结点，并且把尾节点踢出链表

                Node tempNode = new Node(tempNum);

                tempNode.next = result.head;

                result.head.pre = tempNode;

                result.head = tempNode;

                result.tail = result.tail.pre;

                result.tail.next = null;

            } else if (tempNum < result.tail.value) { // 如果此数比尾节点小，那么就遍历链表

                Node currNode = result.tail;

                while (currNode != null) {

                    if (currNode.value == tempNum) { // 如果此数和尾节点相等，那么不需要进行操作，退出遍历

                        break;

                    } else if (tempNum > currNode.value) { // 如果此数比某节点要大，那么插入新节点，并且把尾节点踢出链表

                        Node tempNode = new Node(tempNum);

                        Node nextNode = currNode.next;

                        currNode.next = tempNode;

                        tempNode.next = nextNode;

                        tempNode.pre = currNode;

                        nextNode.pre = tempNode;

                        result.tail = result.tail.pre;

                        result.tail.next = null;

                        break;
                    }

                    currNode = currNode.pre; // 不停向前遍历节点
                }
            }
        }

        long end = System.currentTimeMillis();

        Node cN = result.head;

        while (cN != null) {

            System.out.println(cN.value);

            cN = cN.next;

        }

        System.out.println("用时:" + (start - end) + "ms");
    }
}

双向链表的初始化过程 新增头节点删除尾节点 遍历并添加节点，删除尾节点