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

Question

给定一个N-length 数组B，求 , 的排列[1 .. N]，A即对于所有大于的索引，其中大于B[i]的元素数。AA[i]i

例子：N = 4, B=[1 1 1 0]

输出：A=[3 2 1 4]

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

进一步解释：在 index 之后B[i]的项目数大于A[i]数组中的数。即对于所有大于的索引。例如：这意味着在第三个元素之后有一个大于的元素。A[]iiB[2]=1A[]A[2]

提前致谢

score 3 · Accepted Answer

这似乎可行：从临时列表开始T := [ N, N-1, N-2, ..., 3, 2, 1 ]。这个列表像C# 中0的a 一样被索引。N-1List<int>

拿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], 如下所示：

在 index 处读取和删除1：

在 index 处读取和删除1：

在 index 处读取和删除1：

在 index 处读取和删除0：

编辑：我发现这被称为Lehmer 代码。

score 0 · Accepted Answer

我想到的答案之一是以下算法：

For i = N to 1
   A[i] = N - B[i]
   For j = i+1 to N
      If A[j] <= A[i]
         A[j]--

2 回答 2