arrays - 给定三个等长数组，我如何找到可能的组合数量，其中我以递增的方式从每个数组中选择一个整数

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

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

对于第二个数组的每个项目 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)