如何根据前置大数计数序列还原初始排队编号序列？

算力阿峰

2026-7-21

从计数序列还原排队编号序列的算法实现

问题描述

假设有N个编号为1到N的人随机排成一队，每人对应一个数值，该数值表示其前方编号比自己大的人数。例如序列[2,3,1,5,4]对应的计数序列为[0,0,2,0,1]。需求是反向求解：已知该计数序列，还原初始的排队编号序列。

算法实现思路

采用从后往前构建结果序列的方法：

维护一个包含所有未使用编号的集合（初始为0到N，0仅作为占位不参与实际选择，后续会移除已选编号）
从计数序列的最后一个元素开始遍历，对于当前计数counter，从剩余可用编号中选取倒数第counter+1个元素，将其放入结果序列的对应位置，随后从可用集合中移除该元素

可行C++代码

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

vector<int> restoreQueue(const vector<int>& visibility) {
    int n = visibility.size();
    vector<int> queue(n, 0);
    vector<int> numbers(n+1);
    iota(begin(numbers), end(numbers), 0);
    for (int i = n-1; i>=0;i--){
            int counter = visibility[i];
            cout << "Counter: " << counter <<endl;
            vector<int>::iterator iter;
            iter = numbers.end() - 1 - counter;
            int x = *iter;
            cout << "X: " << x <<endl;
            queue[i] = x;
            numbers.erase(remove(numbers.begin(), numbers.end(), x), numbers.end());
        }
    return queue;
}

int main() {
    vector<int> visibility = {0,1,2};
    vector<int> queue = restoreQueue(visibility);
    cout << "Starting sequence: ";
    for (int i = 0; i < queue.size(); i++) {
        cout << queue[i] << " ";
    }
    cout << endl;
    return 0;
}