问算法建议-在数字列表上搜索

EN

我能想到的将集合上的元素与一些通配符搜索参数进行匹配的唯一方法是遍历列表并找到匹配的元素。

如果搜索速度太慢，您还可以分离列表并并行运行搜索。

我假设你的初始号码列表已经排序好了。如果它没有排序，你最好对它进行排序，因为有了排序列表，你可以用一个非常直接的算法得到数字。但是，如果这不是时间关键型操作，您最好使用哈希表或B-Tree数据结构。B-Tree可以提供log(n)个查询时间。它更容易实现。

有了排序列表，你可以直接跳到正确的元素，如果输入指定了搜索的位置和值，即如果输入只查找位置6，3和0分别为5，9和1的数字，你可以直接跳到索引5,000,000，而不需要查找5,999,999以外的值。

关键的洞察力在于，如果您在位置X查找一个数字(I)，并且您在该位置找到了第一个这样的数字N，那么下一个连续的10^X-1数字将在相同的位置具有I。下一组在X处具有I的数字将在索引N + 10 ^ (X+1)处。

例如，如果您正在查找位置2为5的数字，如果您位于10000500位置，则可以将下一个10^2-1(99)数字读取为与该条件匹配的值。下一组位于位置10000500 + 10^3 = 100001500。

在你的问题中，你有多个这样的条件，所以你从最高位置的数字开始，然后进一步向下移动到较小的位置，并跳到数字集。如果跳转到的下一个集合大于紧靠其上位置的数字所允许的范围，则跳转到该位置的数字所指向的值。

例如，如果您正在查找位置为2的5和位置为1的3的数字，则从10000530开始。下一个10^1编号将与您的标准匹配。仅3的下一组将在10000530 + 10^2 = 10000630，但这超过了5在位置2设置的限制，即99。因此，您可以跳到5指向的下一个集合，即10001530。

这种方法在时间上是线性的，w.r.to输出集，所以你可以有一个巨大的输入，如果你的输出真的很小，这个方法会很快出来。如果您使用B-Tree或类似的方法，它们将取决于输入大小。