java - 算法:从多个有序列表中搜索递增的整数序列

Question

我正在尝试找到最有效的方法来从已排序整数数组(列表)的数组(或列表)中查找整数序列。假设我有这个数组

{
{1, 3, 4, 9, 15},
{5, 10, 13},
{2, 6, 11, 17},
{7, 8, 12}
}

那么解应该返回连续递增数的数组

{ {4, 5, 6, 7}, {9, 10, 11, 12} }

在结果中，4 和 9 来自第一个子数组，5 和 10 来自第二个子数组，依此类推。约束是最终输出中的所有数组必须具有输入中数组数量的固定长度，即输入中的所有数组必须在结果中的每个数组中提供 1 个元素。

我们可以假设输入数组已排序，并且输入数组中没有重复项，例如，在示例中，如果 9 在数组 1 中，我可以假设 9 不会在任何其他输入数组中。

有什么有效的方法吗？除了暴力破解数组，我想不出任何办法。接受使用任何数据结构和算法。

谢谢。

Answer 1

1. 从第一个数组中选取第一个值，并将其保存为prevValue。

2. 在每个输入数组中构建一个位置(索引)数组，并将它们初始化为 0。

3. 遍历输入数组:

   • 给定输入数组的前进位置，直到值为 >= prevValue。
     如果到达输入数组的末尾，停止，你就完成了。

   • 将 prevValue 更新为找到的值。

4. 现在位置数组存储下一个递增值序列的位置。将值保存到结果。

5. 重复第 3 步和第 4 步，直到完成。

---

作为代码，应该是这样的:

private static int[][] findIncrementalSequences(int[][] input) {
    int[] pos = new int[input.length];
    int prevValue = Integer.MIN_VALUE;
    List<int[]> results = new ArrayList<>();
    for (;;) {
        int[] result = new int[pos.length];
        for (int i = 0; i < pos.length; i++) {
            while (pos[i] < input[i].length && input[i][pos[i]] <= prevValue)
                pos[i]++;
            if (pos[i] == input[i].length)
                return results.toArray(new int[results.size()][]);
            prevValue = result[i] = input[i][pos[i]];
        }
        results.add(result);
    }
}

测试

int[][] input = { {1, 3, 4, 9, 15},
                  {5, 10, 13},
                  {2, 6, 11, 17},
                  {7, 8, 12} };
System.out.println(Arrays.deepToString(findIncrementalSequences(input)));

输出

[[1, 5, 6, 7], [9, 10, 11, 12]]

---

更新

如果每个子结果必须是连续递增的值，则可以修改代码以在下一个数字不正好比前一个值高 1 时从 input[0] 重新开始。

以下代码也略有更改，以删除重复的数组查找。

private static int[][] findConsecutiveSequences(int[][] input) {
    int[] pos = new int[input.length];
    int nextValue = Integer.MIN_VALUE, value;
    List<int[]> results = new ArrayList<>();
    for (;;) {
        int[] result = new int[pos.length];
        for (int i = 0; i < pos.length; i++) {
            for (;;) {
                if (pos[i] == input[i].length)
                    return results.toArray(new int[results.size()][]);
                if ((value = input[i][pos[i]]) >= nextValue)
                    break;
                pos[i]++;
            }
            if (i == 0 || value == nextValue) {
                result[i] = value;
                nextValue = value + 1;
            } else {
                i = -1; // Restart with input[0]
            }
        }
        results.add(result);
    }
}

输出

[[4, 5, 6, 7], [9, 10, 11, 12]]