algorithm - 给定一个未排序的整数数组 A，返回一个数组 B，其中 B[i] 是 A[j] 的数量，使得 A[i] > A[j] 而 i < j

Question

示例:A = [5, 3, 8, 7, 2, 1, 4]。然后我们会得到 B = [4, 2, 4, 3, 1, 0, 0]。

有没有办法在 O(n log n) 中做到这一点？

Answer 1

a) 从右到左工作，边走边将值插入带注释的平衡树中。如果您在树中保留注释，告诉您每个节点下方的项目数，那么您可以计算出每个项目右侧的项目数小于您插入时的项目数。这是一棵平衡树，因此每次插入的成本最多为 log n，总成本为 n log n。

b) 分而治之，在每个点将数组分成两半，并按排序顺序返回值和为每一半计算的 B 数组。当你合并时，你需要做一个排序，并且对于数组的左半部分，你需要添加数组右半部分中小于自身的值的数量。您可以将此作为合并的一部分来执行，它仍然需要线性时间，因此成本是合并排序的通常 n log n。