阿裡2015年4月實習生招聘研發崗筆試題——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. 為該算法設計并實作單元測試

void Insert(std::list<int> &Request,int val)
{
    std::list<int>::iterator current = Request.begin();
    while(current!=Request.end() && *current<val) {
        ++current;
    }
    Request.insert(current,val);
}

void Solution(std::istream &In)
{
    std::list<int> Request;
    int next = 1;
    int val;
    while(In>>val) {
        if(val==next) {
            std::cout << val << ' ';
            ++next;
            while(!Request.empty() && Request.front()==next) {
                std::cout << Request.front() << ' ';
                Request.pop_front();
                ++next;
            }
            std::cout << std::endl;
        } else {
            Insert(Request,val);
        }
    }
}