检查数组中所有a[k]<a[i]<a[j]的三胞胎数目的最佳方法

Question

我正在解决一个问题，在这个问题中，我必须在数组中找到Ai、Aj和Ak的三胞胎数量，例如Ak < Ai < Aj和i < j < k。

用蛮力解决这个问题是微不足道的，但它的复杂性是O(N^3)。解决这一问题的最佳方法是什么？

Answer 1

这是一种O(n^2)方法，它修复i并以反向顺序遍历数组的其余部分，跟踪ai下面的元素数。

def count_triplets(a):
    """Count the number of triplets a[k]<a[i]<a[j] for i<j<k"""
    t = 0
    for i,ai in enumerate(a):
        kcount = 0 # The number of elements smaller than a[i]
        for x in a[:i:-1]:
            if x<ai:
                kcount += 1
            elif x>ai:
                t += kcount
    return t


A=[1,6,3,4,7,4]
print count_triplets(A)

工作实例

对于给定的数组数组，有趣的情况是，i等于1，ai等于6。

该程序现在对数组中的其余条目进行反向工作，如下所示：

x = 4
x < ai so kcount increased to 1
x = 7
x > ai so t increased by kcount, i.e. t increased to 1
x = 4
x < ai so kcount increased to 2
x = 3
x < ai so kcount increased to 3

I的所有其他值最终都不会增加t，所以t的最终值是1。

测试代码

Hackerrank站点希望代码支持多个输入。下面的代码通过了所有测试。

N=input()
for n in range(N):
    A=map(int,raw_input().split())
    print count_triplets(A)