5

我有一个随机数数组让我们说：

[10,11,12,14,15,16,17,18,19,20, 11 , 12 , 14,25,25,26,27,28,29 ]

我必须检测重复的序列（女巫实际上是错误的）

长度大于特定数字 (2)。

有什么好的算法吗？

我现在拥有的：

int minLenght = 3;
int[] data = {1,2,3};

for(int i = 0; i < data.length; i++){
    for(int j = 0; j < data.length; j++){
        if ( data[i] == data[j]){
            int l = 0;
            int ii = i;
            int jj = j;
            while(data[ii] == data[jj]){
                ii++;
                jj++;
                l++;
            }
            if(l >= minLenght){
                print('['+i+'-'+ii+'] same as ['+j+'-'+jj+']');
            }
        }
    }
}
4

3 回答 3

4

一种方法是将长度为 L（比您的特定长度大一个）的序列存储在哈希表中。

如果你发现一个序列已经在哈希表中，那么你发现了一个长度 >= L 的重复。

例如 Python 代码

A=[10,11,12,14,15,16,17,18,19,20,11,12,14,25,25,26,27,28,29]
S=set()
L=2+1
for i in xrange(len(A)-L+1):
    key=tuple(A[i:i+L])
    if key in S:
        print i
    else:
        S.add(key)

这会打印出长度大于 2 的重复序列的位置。

于 2012-11-27T21:29:38.397 回答
0

我不知道是否有一个特殊的算法，但我的建议是这样的：

loop1 over array[i]:
  loop2 over array[j] starting with i+1:
    dist=array[j]-array[i];
    if dist==specific_number:
      array_result.append(array[i] +""+""+array[j])

这将是我的简单逻辑。

于 2012-11-27T21:30:03.543 回答
0

您可以使用正则表达式，但显示的列表格式不规则。我在下面使用 Python 并将列表格式“正则化”，然后将其转换为字符串，然后再应用正则表达式以查找重复的数字/非数字序列：

>>> import re
>>> numbers = [10,11,12,14,15,16,17,18,19,20, 11, 12, 14,25,25,26,27,28,29]
>>> sep = ', '
>>> txt = sep + sep.join(str(x) for x in numbers) + sep
>>> txt
', 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 11, 12, 14, 25, 25, 26, 27, 28, 29, '
>>> re.search(r'\D((?:\d+\D+){2,}).*\1', txt).groups()
('11, 12, 14, ',)

我通常会尽量减少对正则表达式的使用，但这确实会检测到重复。

于 2012-11-28T07:03:54.307 回答