阿里2015 实习笔试题笔记分布式系统中的RPC请求经常出现乱序的情况面试题目

分布式系统中的RPC请求经常出现乱序的情况。
写一个算法来将一个乱序的序列保序输出。例如,假设起始序号是1，对于(1, 2, 5, 8, 10, 4, 3, 6, 9, 7)这个序列，输出是:
1
2
3, 4, 5
6
7, 8, 9, 10

上述例子中，3到来的时候会发现4,5已经在了。因此将已经满足顺序的整个序列（3, 4, 5）输出为一行。

要求：
1. 写一个高效的算法完成上述功能，实现要尽可能的健壮、易于维护
2. 为该算法设计并实现单元测试

不知道是不是所有数据都满足。。。

#include #include #include #include using namespace std; struct node { int key; int index; }; bool cmp(node a,node b) { return a.key < b.key; } ; class Solution { public: void print(int a[],int length) { node *val = new node[length]; for(int i = 0; i < length; ++i) { val[i].key = a[i]; val[i].index = i; } sort(val,val+length,cmp); int index_tem = val[0].index; for(int i = 0; i < length; ++i) { printf("%d",val[i].key); if(i != length -1 && (val[i].index > val[i+1].index || val[i+1].index < index_tem)) { printf(","); } elseif(i != length -1) { printf("\n"); index_tem = val[i+1].index ; }} delete [] val; } }; int main() { Solution s; int t[10] = {1, 2, 5, 8, 10, 4, 3, 6, 9, 7}; s.print(t,10); getchar(); return 0; }