1

P = [a1, a2, ... , aN]第一个自然数的排列N可以用一个倒数 I = [i1, i2, ... , iN]列表来表示，其中iK告诉我们有多少数大于在排列K中之前可以找到的数。KP

示例： if P = [3, 1, 4, 2], then I = [1, 2, 0, 0]（3 放在 1 之前，3 和 4 放在 2 之前，而 3 和 4 之前没有任何更大的数字）。

有一个明显的算法可以将排列从标准形式转换为反转形式并运行O(N^2)（我们只需遵循定义和计数）。逆变换也是如此（稍微不那么直接）。

有没有时间复杂度较低的算法？

4

2 回答 2

1

有一个简单的迭代动态规划算法来解决这个问题：对于从 1 到n（排列长度）的所有 i，取数字并查看左侧有i多少元素已经被看到。由于我们按递增顺序处理，我们知道未看到的元素是大于- 的元素，因此我们计算并记下这些元素的数量。诀窍是引入一个外部列表，而不是跟踪已经看到的元素。PiiiP

首先，让我们看看如何以方式做到这O(n^2)一点。例如，如果P=[4, 3, 2, 1]，那么算法将按如下方式执行：

  1. 创建一个tree初始化为零的结构。如果迭代算法已经看到j第 j 个位置的元素，则它的位置保持“1” 。P

  2. 取 1，确定pos==3。在 中写下“1” tree[pos]。计算num_seen=sum(tree[0:3])等于 0。写pos - num_seen + 1在 处I[0]。在这之后：tree = [0, 0, 0, 1], I = [3, 0, 0, 0]

  3. 取 2，在树 [1] 中写下“1”，在 I[1] 处写下 1。tree = [0, 1, 0, 1], I=[3,1,0,0].

  4. 取 3，在树[2] 中写下“1”，在 I[2] 中写下 0。tree = [0, 1, 1, 1], I=[3,1,0,0].

  5. 取 4，在树 [0] 中写下“1”，在 I[3] 处写下 0。tree = [1, 1, 1, 1], I=[3,1,0,0].

第二个技巧是使用有效的数据结构来及时计算所见元素的数量，O(n log n)而不是O(n^2)像上面那样。

这是使用 Fenwick 树快速计算可见元素数量的 Python 代码：

def ft_sum(tree, a, b):
  if a == 0:
      s = 0;
      while  b >= 0:
          s += tree[b];
          b = (b & (b + 1)) - 1
      return s
  return ft_sum(tree, 0, b) - ft_sum(tree, 0, a - 1)

def ft_adjust(tree, k, v):
    while k < len(tree):
        tree[k] += v
        k |= k + 1

def calcI(P):
    n = len(P)
    tree = [0] * n
    I = [0] * n
    positions = [0] * n
    for i in xrange(n):
        positions[P[i]-1] = i
    tree = [0] * n
    for i in xrange(n):
        pos = positions[i]
        ft_adjust(tree, pos, 1)
        num_seen = ft_sum(tree, 0, pos)
        I[i] = pos - num_seen + 1
    return I
于 2016-01-06T11:35:30.247 回答
0

同时，我找到了一个简单的解决方案，关于伪代码，它也适用于O(n log n).

initialize AVL-tree T
initialize array I of length n
for i = 1, 2, ... , n:
    I[P[i]] = T.countGreaterThan(P[i])
    T.add(P[i])
于 2016-01-06T12:45:05.710 回答