阿里巴巴 2015 实习笔试题 分布式系统中的RPC请求经常出现乱序的情况 写一个算法来将一个乱序的序列保序输出

本文主要是介绍阿里巴巴 2015 实习笔试题 分布式系统中的RPC请求经常出现乱序的情况 写一个算法来将一个乱序的序列保序输出，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

转载请注明出处：http://blog.csdn.net/tsx86/article/details/44883601

分布式系统中的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. 为该算法设计并实现单元测试

基本思想是将每一行存入一个链表结点，data表示起始数据，len表示每行元素个数。

貌似效率不是很高，有时间的时候改进下。

struct ListNode  
{int data;int len;ListNode* next;  
}; void InsertNode(ListNode *&pHead, ListNode *pNode)
{ListNode * pTmp = NULL;if(pNode == NULL){cout << "pNode is NULL!" << endl;return;}if(pHead == NULL){pHead = pNode;}else{for(pTmp = pHead;pTmp->next != NULL; pTmp = pTmp->next);pTmp->next = pNode;	}
}void SortAndPrint(int a[], int n)
{ListNode *pHead = NULL;ListNode *temp = NULL; int i = 0;int data = 0;int dataLen = 0;while(i < n){int j = 0;int len = 0;int moreNum = a[i];int lessNum = a[i];//查找小于一个数的连续数出现次数 while(j < i){if(a[j] == lessNum-1){j = 0;lessNum--;continue;}j++; }//只有小于一个数的所有数均出现时才存数据if(lessNum == 1){j = 0;while(j < i){if(a[j] == moreNum+1){len++;moreNum++;j = 0;continue;}j++;}ListNode *p = (ListNode*)malloc(sizeof(ListNode));memset(p, 0, sizeof(ListNode));p->data = a[i];p->len = len;p->next = NULL;InsertNode(pHead, p);}i++;}//按顺序打印序列 for(temp=pHead; temp!=NULL; temp=temp->next){dataLen = temp->len;data = temp->data;while(dataLen){printf("%d,",data++);dataLen--;}printf("%d\n",data);}//释放资源 ListNode *prev = NULL;ListNode *curr = pHead;while(curr!=NULL){prev=curr;curr=curr->next;if(prev != NULL){free(prev);prev = NULL;}}
}

这篇关于阿里巴巴 2015 实习笔试题 分布式系统中的RPC请求经常出现乱序的情况 写一个算法来将一个乱序的序列保序输出的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---