首页 > 试题广场 >

查找重复序列

[编程题]查找重复序列

热度指数：919 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知某序列S=<e1,e2,…,en>，序列中的元素类型为整数（en <= 2^10），序列的长度为可变长度。
现在有若干序列S1，S2,…,Sn，现在要求设计一种算法，找出这些重复的序列。输出重复序列的序号，如果有多组重复，需全部输出。

所有序列中的数字个数加起来，小于1000000，序列个数小于10000个。

例如现有3个序列
S1=<65,43,177,655>
S2=<1,2,3,4,5,6,7>
S3=<65,43,177,655,3>
这时序列无重复。又如
S1=<65,43,177,655,3>
S2=<1,2,3,4,5,6,7>
S3=<65,43,177,655,3>
这时序列有重复。

输入描述:

第一行为一个正整数N，N>=1且N<10000

接下来为2*N数据，每两行表示一个序列，序列的第一行为序列长度L，第二行为序列的数字，一共L个

输出描述:

重复序列的序号，每一行X个数字，表示一组相同的序列，这一组相同序列共有X个，输出这X个序列的序号

示例1

输入

11
10
794 472 991 500 615 872 518 827 673 203 
1
427 
7
367 718 202 187 683 321 831 
10
1023 78 310 816 158 500 518 705 553 470 
8
205 190 306 492 166 49 791 961 
6
665 211 1009 614 15 683 
2
195 946 
3
678 198 495 
8
205 190 306 492 166 49 791 961 
5
83 74 1023 453 692 
2
176 157

输出

4 8

算法知识视频讲解

Python

pein531

这个题用python的有序表会更加方便一些。构建一个顺序表，以序列为key，以序列的编号列表作为value，在输入阶段将序列往这个顺序表里面加就行；在输出阶段直接把value长度大于1的打印出来就可以了。

from collections import OrderedDict

if __name__ == "__main__":
    n = int(input())
    m = OrderedDict()
    for i in range(n):
        L = int(input())
        seq = input().strip()
        if seq in m:
            m[seq].append(str(i))
        else:
            m[seq] = [str(i)]
    hasDuplicates = False
    for k in m:
        if len(m[k]) > 1:
            hasDuplicates = True
            print(" ".join(m[k]))
    if not hasDuplicates:
        print("no")

发表于 2021-12-06 21:10:21 回复(0)