给定 n 个数字的排列数组，计算编号。元组 (i,j,k,l,m) 使得 i<j<k<l<m 和 a[i]<a[k]<a[j]<a[m]<a[l]

Question

对于软件开发面试的硬算法轮，我最近被问到这个问题。我能够使用 Brute Force/Recursion 做到这一点，不确定预期的方法，对此有任何帮助吗？

Given an array of permutation of n numbers, calculate the noumber of tuples (i,j,k,l,m) such that i<j<k<l<m and a[i]<a[k]<a[j]<a[m]<a[l].

我的方法 -> 使用递归尝试给定数组中 (i,j,k,l,m) 的所有元组中的每一个，并仅考虑满足条件的元组，例如 N 选择 5 ，由于这具有指数时间复杂度，我想使其成为三次方或二次方

Answer 1

我会大量使用 Quadtrees 之类的东西。四叉树允许您在 2d 中放置一堆点，然后有效地搜索区域。要么找到点，要么只是计算它们。（存储每个节点中的点数，然后计数会变得更快，因为当您在所需区域中完全有一个正方形时，您可以停止。）

一个有用的四叉树是将排列视为一系列 n 个点 (i, a[i])。我们可以使用它来查找 i 在一个范围内而 a[i] 在另一个范围内的所有情况。称那棵树为 perm.

第二个有用的四叉树是将所有反转 i < j 和 a[j] < a[i] 映射到点 (i, a[j])。称那棵树为 invert.

现在您的搜索如下所示：

search invert to find all inversions (j, k):
    x = count i < j with a[i] < a[k] (search perm)
    y = count inversions (l, m) with k < l and a[j] < a[m] (search invert)
    add x*y to total

我相信填充 perm 将花费时间 O(n log(n))，填充 invert 将花费 O(n^2 log(n))，每次搜索以获取计数应该类似于 O((log(n))^2)。（不确定那个。）由于有 O(n^2) 个反转，总性能应该类似于 O((n log(n))^2).

给定 n 个数字的排列数组，计算编号。元组 (i,j,k,l,m) 使得 i<j<k<l<m 和 a[i]<a[k]<a[j]<a[m]<a[l]

Given an array of permutation of n numbers calculate the no. of tuples (i,j,k,l,m) such that i<j<k<l<m and a[i]<a[k]<a[j]<a[m]<a[l]

algorithm

data-structures