对于这种模式有什么优雅的解决方案?多级搜索

如果您事先订购阵列,搜索速度会更快。您可以从较小的数组开始,然后二进制搜索每个数组上的预期数字。这将是O(n) K logM),n是最小数组的大小,k是数组的个数,M是较大数组的大小

如果使用Hashmaps而不是数组,则可以更快地完成此操作。这将允许您在O(n*k)中搜索。

为了简单起见,我将从第一个数组开始

//note the 1-based arrays
for (i : 1 until allArrays[1].size()) {
  baseNumber = allArrays[1][i];
  for (j: 2 until allArrays.size()) {
    expectedNumber = function(baseNumber);
    if (!find(expectedNumber, allArrays[j]))
        break;
    baseNumber = expectedNumber;
  }
}

你可以做一些空值检查,并在那里添加一些布尔值来知道序列是否存在

视情况而定:

1. 如果数组以随机顺序出现,并且您需要有限的空间,那么暴力是唯一的解决方案。O(无) )时间(k=3),O(1)空间。
2. SHA1(next_elem) xor SHA1(prev_elem) == 0x1234
3. ^K )时间,O(kN)空间(b=满足谓词的下一个元素的最大数目(上一个元素)
4. 如果数组是排序和有界的,还可以使用二进制搜索而不是哈希表来避免使用空格。O(对数N) +b类 )时间,O(1)空间。

消耗高达O(Nb)的一般方法 )空间是通过连续过滤来构建解决方案,例如。

solutions = [[1], [2], ... [N]]

filterSolution (Predicate, curSols, nextElems) {
   nextSols = []
   for each curSol in curSols:
      find elem in nextElems that satisfy the Predicate
      append elem into a copy of curSol, then push into nextSols
   return nextSols
}

for each levels:
  solutions = filterSolution(Predicate, solutions, all elems in this level)
return solutions

我会保持所有向量 heaps 所以我可以 O(log n) k 向量你会得到一个复杂的 O(k * log n)

如果谓词保留数组中的顺序(例如,在您的示例中,如果值都保证为非负),则可以调整合并算法。考虑每个数组的关键值是结束值(在所有数组都需要应用谓词后得到的值)。

如果谓词没有保留顺序(或者数组没有按顺序开始),您可以先按结束值排序,但是这样做的必要性表明另一种方法可能更好(比如其他地方建议的哈希表)。

基本上,检查所有数组的下一个结束值是否相等。如果没有,请跨过最低的一个(仅在一个数组中)并重复。如果三者都相等,那就是一个(可能的)解决方案——在搜索下一个之前,先遍历所有三个。

“可能”的解决方案,因为您可能需要进行检查-如果谓词函数可以将多个输入值映射到同一输出值,则可能会出现某些数组中的值(而不是第一个或最后一个)错误的情况。

编辑 -当谓词没有将每个输入映射到一个唯一的输出时,可能会有更大的问题——此时无法思考。基本上,合并方法可以很好地工作,但只适用于某些类型的谓词函数。