【左神算法】一种接收消息并按顺序打印的结构设计

妖狐艹你老母 2021-11-27 05:40 251阅读 0赞

> **题目：一种消息接收并打印的结构设计：已知一个消息流会不断地吐出整数 1 ~ N，但不一定按照顺序吐出。如果上次打印的数为i，那么当 i + 1 出现时，请打印 i + 1 及其之后接收过的并且连续的所有数，直到 1 ~ N 全部接收并打印完，请设计这种接收并打印的结构。**
> 
> 例如：  
> 消息流吐出 2，一种结构接收而不打印 2，因为 1 还没出现；  
> 消息流吐出 1，一种结构接收 1，并且打印：1，2。  
> 消息流吐出 4，一种结构接收而不打印 4，因为 3 还没出现。  
> 消息流吐出 5，一种结构接收而不打印 5，因为 3还没出现。  
> 消息流吐出 7，一种结构接收而不打印 7，因为 3 还没出现。  
> 消息流吐出 3，一种结构接收 3，并且打印：3，4，5。  
> 消息流吐出 9，一种结构接收而不打印 9，因为 6 还没出现。  
> 消息流吐出 8，一种结构接收而不打印 8，因为 6 还没出现。  
> 消息流吐出 6，一种结构接收 6，并且打印：6，7，8，9。  
>   
> 【要求】消息流最终会吐出全部的 1 ~ N，当然最终也会打印完所有的 1 ~ N，要求接收和打印 1 ~ N 的整个过程，时间复杂度为 O(N)。

**分析：**

** 结构：单向链表 + 两个 HashMap<Integer, Node> 【头表和尾表记录了所有连续区间的开头和结尾】**

*  对于接收的每一个数，如果能和之前接收的数连续起来，就归入之前的数据区间中，如果不能就单独成为一个区间。每一个区间使用单链表结构实现。
 *  例如，接收 2 的时候，根据 2 生成一个单链表节点，因为没有其他元素，所以它单独成一个区间\[2\]；接收 1 的时候，根据 1 生成一个节点，然后发现之前的区间 \[2\] 可以和 1 连续起来，所以将该节点归入区间 \[2\]，此时该区间更新为 \[1,2\]；接收 4 的时候，根据 4 生成一个节点，没有区间可以和它连续起来，所以它单独成一个区间 \[4\]；然后接收 5，和 4 连续起来，\[4\] 区间更新为 \[4,5\]；然后接收 3，3 可以和 \[1,2\] 连续起来，也可以和 \[4,5\] 连续起来，所有整体可以归入一个区间 \[1~5\]。
 *  为了加速合并的过程，使用两个哈希表 headMap 和 tailMap，分别用来存放区间的开头节点和结尾节点。假设一个数 n 被接收，首先将 n 的节点添加到 headMap 和 tailMap 中。然后在 headMap 中寻找是否有 n + 1 元素，如果有，说明以 n + 1 开头的区间可以向左再添加一个数 n，所以将区间扩充 1 位，将 headMap 中的 n + 1 元素和 tailMap 中的 n 元素删除。然后在 tailMap 中寻找是否有 n - 1 元素，如果有，说明以 n - 1 结尾的区间可以向右再添加一个数 n，所以将区间扩充 1 位，将 tailMap 中的 n - 1 元素和 headMap 中的 n 元素删除。
 *  什么时候打印呢？设置一个变量 lastPrint，表示上一次打印的最后一个元素是什么，然后每次在 headMap 中寻找是否有 lastPrint + 1 元素，如果有的话，将整个以 lastPrint + 1 开头的区间的数都打印，然后更新 lastPrint。

public class ReceiveAndPrintOrderLine {
    
        public static class Node{
            public int num;        // 节点标号
            public String content; // 节点内容
            public Node next;
    
            public Node(int num, String content){
                this.num = num;
                this.content = content;
            }
        }
    
        private HashMap<Integer, Node> headMap = new HashMap<>();
        private HashMap<Integer, Node> tailMap = new HashMap<>();
        private int lastPrint = 0;
    
        public void receive(int num, String content){
            if(num < 1){
                return;
            }
            // 将消息标号和内容构建成链表节点的形式
            Node current = new Node(num, content);
            headMap.put(num, current);
            tailMap.put(num, current);
            // 这个数前面有一个链表，它要成为新的尾部，它也不再是头了
            if(tailMap.containsKey(num - 1)){
                // 插入到原来链表的尾部
                tailMap.get(num - 1).next = current;
                tailMap.remove(num - 1);  // num-1不再是尾部了
                headMap.remove(num); // num不再是头部了
            }
            // 这个数后面有一个链表，它将成为新的头，它也不再是尾了
            if(headMap.containsKey(num + 1)){
                current.next = headMap.get(num + 1);
                tailMap.remove(num);    // num不再是尾结点了
                headMap.remove(num + 1);  // num+1不再是头结点了
            }
            // 判断打印时机：现在的头结点是否是lastPrint+1
            if(headMap.containsKey(lastPrint + 1)){
                print();
            }
        }
    
        public void print(){
            Node node = headMap.get(++lastPrint);
            headMap.remove(node);
            while(node != null){
                System.out.println(node.num + " : " + node.content);
                node = node.next;
                lastPrint++;
            }
            tailMap.remove(--lastPrint);
            System.out.println();
        }
    }