如何从这个序列生成反向序列？

Question

我的算法一直有问题。假设有 N 个人在排队，每个人都有一个编号（从 1 到 N）。因此，如果有 3 个人，则有一个人的号码为 1，一个人的号码为 2，一个人的号码为 3。他们以随机顺序站立，每个人都分配了第二个数字，告诉他们有多少人站在他们面前比他们大的数字。例如，如果有 5 个人在排队，每个人都在向左看，我们可以有这样的组合：<- 2 <- 3 <- 1 <- 5 <- 4 That means that:

数字为 2 的人有 [0] 个人站在他面前，数字更大，因为没有人站在他面前 数字为 3 的人有 [0] 个人站在他面前，尽管他前面有 1 个人，但数字更大 数字为 1 的人有 [2] 个人站在他面前，数字更大（2 和 3） 编号为 5 的人有 [0] 个人站在他的前面，尽管他前面有 3 个人 数字为 4 的人有 [1] 个人站在他面前，数字更大的人 (5) 因此，对于序列 [2,3,1,5,4]，结果序列为 [0,0,2,0,1]。

我的问题是相反的。如何获得将结果作为输入的起始序列。

#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 max = *max_element(numbers.begin(),numbers.end());
            cout << "Max: " <<max << endl;
            int counter = visibility[i];
            cout << "Counter: " << counter <<endl;
            int x = max - counter;
            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, 0,0 , 3, 1};
    vector<int> queue = restoreQueue(visibility);
    cout << "Starting sequence: ";
    for (int i = 0; i < queue.size(); i++) {
        cout << queue[i] << " ";
    }
    cout << endl;
    return 0;
}

我试过用 C++ 做这个，但 Dave 的方法不起作用

Answer 1

从后往前，将值解释为从当前值的最大值向下多少个值。

让我们举个例子：[0,0,2,0,1]

1. Unk: [1,2,3,4,5], num_greater: 1，所以这是从最大剩余值减1，即4。ans = [?,?,?,?,4]
2. Unk: [1,2,3, 5], num_greater: 0，所以这是从最大剩余值向下减0，即5。ans = [?,?,?,5,4]
3. Unk: [1,2,3, ], num_greater: 2，所以这是从最大剩余值减去 2，即 1。ans = [?,?,1,5,4]
4. Unk: [ 2,3, ], num_greater: 0，所以这是从最大剩余值减0，即3。ans = [?,3,1,5,4]
5. Unk: [ 2 ], num_greater: 0，所以这是从最大剩余值向下减0，即2。ans = [2,3,1,5,4]

来自评论：输入是 [0,0,0,3,1]

1. Unk：[1,2,3,4,5]，往下1就是4，所以ans = [?,?,?,?,4]
2. Unk: [1,2,3, 5], 3 down 是 1, 所以 ans = [?,?,?,1,4] ...其余的都是 0，因此 ans 将按降序取余数：ans = [2,3,5,1,4]

我想我明白评论者做错了什么。 3 down 并不意味着减去 3，而是在剩余值列表中向下 3，即 1，而不是 2。

Answer 2

这个答案描述了一种使用 O(1) 额外空间并具有 O(n^2) 时间复杂度的简单方法。

输出数组从头开始每次更新一个元素。 输出数组中的零是尚未赋值的条目。

示例输入

[0,0,2,0,1]

将在输出数组中产生以下更新序列：

[0,0,0,0,0] start with all zeros
[1,0,0,0,0] input[0] can only be 0, and output[0] will always start as 1
[1,2,0,0,0] input[1] is 0, so output[1] is the largest value, which is 2
[2,3,1,0,0] input[2] is 2, so increment the two largest values, and put 1 at the end
[2,3,1,4,0] input[3] is 0, so output[3] is the largest value, which is 4
[2,3,1,5,4] input[4] is 1, so increment the largest value, and put 4 at the end

在伪代码中（使用从零开始的索引），算法是：

N is the number of non-zero elements in the output array.  
X is a number taken from the input array.  
Y is a non-zero number in the output array.  

N = 0  
for each number X in the input array:
   for each number Y in the output array:
      if Y > N-X
         increment Y
   put N-X+1 at index N in the output array
   increment N