给定一个 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]
.
提前致谢
最佳答案
这似乎可行:从一个临时列表开始 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 .
关于arrays - 当给定大于 i 的索引的项目数大于 a[i] 时,生成输出数组 A[],我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18423657/