给定三个相等长度的数组,我如何找到可能的组合数,其中我以逐渐增加的方式从每个数组中选择一个整数

Question

假设我有三个n长度的数组:

first = [19, 29, 60];
second = [20, 12, 30];
third = [26, 60, 90];

如果不迭代三个嵌套循环,找到可能组合总数的最佳方法是什么,我可以从第一个数组中选择一个整数,然后从第二个数组中选择一个更大的整数,然后从第三个数组中选择一个更大的整数.基本上,一个组合是:

first[i] < second[j] < third[k]
for example: 19 < 30 < 90 or 29 < 30 < 60

上例中的组合总数为7.获得此数字的最有效方法是什么？

Answer 1

对所有数组进行排序 (数组长度为N的复杂度O(NlogN))

对于B[i]第二个数组中的每个项目,获取第一个数组中较小项目的L数量和第三个数组中较大项目的数量R

添加L*R到结果中

(线性复杂性,因为L只能随着增加而i增加而且R只能减少)

第二阶段的伪代码:

 ia = 0
 ic = 0
 for ib in range(N):
     while (A[ia] < B[ib]):
         ia++
     while (C[ic] <= B[ib]):
         ic++
     result += ia * (N - ic)

整体复杂性是 O(NlogN)