arrays - 当给定大于 i 的索引的项目数大于 a[i] 时，生成输出数组 A[]

Question

给定一个 N -长度数组 B , 找到 [1 .. N] 的排列, A , 这样 B[i]是 A 中的元素数大于 A[i]对于所有大于 i 的指数.

示例:N = 4, B=[1 1 1 0]

输出:A=[3 2 1 4]

谁能帮我解决这个问题的算法？

进一步说明:B[i]项目数量大于 A[i]在数组中 A[]索引后 i .即对于所有大于 i 的指数.例如:B[2]=1这意味着在 A[] 中的第三个元素之后有一个元素大于A[2] .

提前致谢

Answer 1

这似乎可行:从一个临时列表开始 T := [ N, N-1, N-2, ..., 3, 2, 1 ] .此列表索引自 0通过N-1像List<int>在 C# 中。

取T[B[0]] .那是结果数组的第 0 个成员，所以设置 A[0] := T[B[0]] .从 T 中删除此号码.榜单T现在少了一个元素。现在已编入索引 0通过N-2 .

然后设置A[1] := T[B[1]] , 并从 T 中删除该数字.等等，A[i] := T[B[i]] , 其中T在任何时候都只包含直到那时“未使用”的号码。

在伪代码中:

set T := [ N, N-1, N-2, ..., 3, 2, 1 ]
for (i from 0 through N-1)
    A[i] := T[B[i]]
    T.RemoveAtIndex(B[i])

问题中的例子，B=[1 1 1 0] ，是这样的:

• T = [ 4, 3, 2, 1 ], A = [ ]

在索引 1 处读取并删除:

• T = [ 4, 2, 1 ], A = [ 3 ]

在索引 1 处读取并删除:

• T = [ 4, 1 ], A = [ 3, 2 ]

在索引 1 处读取并删除:

• T = [ 4 ], A = [ 3, 2, 1 ]

在索引 0 处读取并删除:

• T = [ ], A = [ 3, 2, 1, 4 ]

---

编辑:我发现这叫做 Lehmer codes .