java算法:从多个有序列表中搜索增量整数序列
我试图找到一种最有效的方法,从一个数组(或列表)中找到一个整数序列。 假设我有这个数组
{
{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不会在任何其他输入数组中
有什么有效的方法吗?除了用蛮力强迫阵列外,我什么都想不出来。可以使用任何数据结构和算法
谢谢
# 1 楼答案
从第一个数组中选取第一个值,并将其另存为
prevValue
在每个输入数组中构建一个位置(索引)数组,并将其初始化为0
迭代输入数组:
前进给定输入数组的位置,直到值为
>= prevValue
如果到达输入数组的末尾,停止,就完成了
将
prevValue
更新为找到的值现在,位置数组存储下一个递增值序列的位置。将值保存到结果
重复步骤3和4,直到完成
作为代码,应该是这样的:
测试
输出
更新
如果每个子结果必须是连续递增的值,那么如果下一个数字不比上一个值高出1,则可以修改代码以在
input[0]
处重新启动为了删除重复的数组查找,下面的代码也做了轻微的更改
输出