数据结构设计题(消息流)

• 题目
• 一、解题思路
• 代码

已知一个消息流会不断地吐出整数 1~N，
但不一定按照顺序依次吐出
如果上次打印的序号为i， 那么当i+1出现时
请打印 i+1 及其之后接收过的并且连续的所有数
直到1~N全部接收并打印完
请设计这种接收并打印的结构

输入可以保证,从0号到n-1号都一定会很全的给你,但是不一定按照原始顺序,我们要求整个这个黑盒接收N条数据打印N条数据,以及它内部所有的调整代价,整体复杂度O(N)

使用两个哈希表,分别记录头和为尾,

如图,(3,c)进入,头表记录3-(3,c),尾表记录3-(3,c)

此时,(5,e)进入,查询头表有没有6,如果没有,头表加入5-(5,e),查询尾表有没有4,没有,加入5

此时加入了4,发现头表有5,因此把5连到4的尾部,删除5节点
发现尾表有3,4连在3的尾部,删除3节点
继续看,在头表还有3,4连在3的尾部,删除4节点
在尾部还有5,5连在4的尾部

因此在加入一个节点n,查询头表是否有n-1,如果有,合并
查询尾表是否有n+1,如果有,合并

	//定义节点
	public static class Node {
		public String info;
		public Node next;

		public Node(String str) {
			info = str;
		}
	}

	public static class MessageBox {
		private HashMap headMap;
		private HashMap tailMap;
		//当前等待哪个数,当这个数出现,输出表里有的数
		private int waitPoint;

		public MessageBox() {
			headMap = new HashMap();
			tailMap = new HashMap();
			waitPoint = 1;
		}

		// 消息的编号，info消息的内容, 消息一定从1开始
		public void receive(int num, String info) {
			if (num < 1) {
				return;
			}
			Node cur = new Node(info);
			headMap.put(num, cur);
			tailMap.put(num, cur);
			// 建立了num~num这个连续区间的头和尾
			// 查询有没有某个连续区间以num-1结尾
			if (tailMap.containsKey(num - 1)) {
				tailMap.get(num - 1).next = cur;
				tailMap.remove(num - 1);
				headMap.remove(num);
			}
			// 查询有没有某个连续区间以num+1开头的
			if (headMap.containsKey(num + 1)) {
				cur.next = headMap.get(num + 1);
				tailMap.remove(num);
				headMap.remove(num + 1);
			}
			if (num == waitPoint) {
				print();
			}
		}

		private void print() {
			Node node = headMap.get(waitPoint);
			headMap.remove(waitPoint);
			while (node != null) {
				System.out.print(node.info + " ");
				node = node.next;
				waitPoint++;
			}
			tailMap.remove(waitPoint-1);
			System.out.println();
		}