四字之字形

Question

我看到了这个有趣的问题，想知道是否有更多方法可以解决它：

Given a permutation of numbers from 1 to n, count the number of quadruples indices (i,j,k,l) such that i<j<k<l and A[i]<A[k]<A[j]<A[l]

例如

输入：[1,3,2,6,5,4]
输出：1 (1,3,2,6)

所需的算法是 O(n^2)

方法：我尝试使用堆栈以类似于 Leetcode 132 pattern 的方式解决它 - 但它似乎失败了。

def get_smaller_before(A):
    smaller_before  = [0] * len(A)
    for i in range(len(A)):
        for j in range(i):
            if A[j] < A[i]:
                smaller_before[i] += 1
    return smaller_before

def get_larger_after(A):
    larger_after = [0] * len(A)
    for i in range(len(A)):
        for j in range(i+1, len(A)):
            if A[i] < A[j]:
                larger_after[i] += 1
    return larger_after

def countQuadrples(nums):
    if not nums:
        return False
    smaller_before      = get_smaller_before(nums)
    larger_after        = get_larger_after(nums)
    counter             = 0
    stack = []
    for j in reversed(range(1, len(nums))):
        # i < j < k < l
        # smaller_before < nums[k] < nums[j] < larger_after
        while stack and nums[stack[-1]] < nums[j]:
            counter += smaller_before[j] * larger_after[stack[-1]]
            stack.pop()
        stack.append(j)
    return counter

有没有人有更好的主意？

Answer 1

你需要的是某种二维树，它可以让你快速回答“k 之后有多少点的值大于 A[j]”的问题，以及“如何j 之前的许多点的值小于 A[k]？”这些通常是 O(n log(n)) 构建的时间，这些查询应该运行及时 O(log(n)^2)).

存在许多这样的数据结构。一个选项是 Quadtree 的变体。你把每个数组元素变成一个点，x 坐标是数组中的位置，y 坐标是它的值。你的查询只是计算一个盒子里有多少元素。

现在您可以对所有 j, k 进行双循环，并计算有多少锯齿形四元组将它们作为内部对。

四字之字形

ZigZag Quadruples

python

algorithm

permutation