C/C++ 关于相等元素编程问题

Question

1.问题描述元素唯一性问题：给出一个整数集合，假定这些整数存储在数组A[1…n]中，确定它们中是否存在两个相等的元素。请设计出一个有效算法来解决这个问题，你的算法的时间复杂性是多少？  输入：输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n (n<=500)，表示整数序列的长度，第二行给出整数序列，整数之间用一个空格隔开。输出：对于每个测试例输出一行，若该组测试例中存在两个相等的元素则输出”Yes”，否则，输出”No”。每个测试例的输出数据用一行表示。3. 测试数据输入：3      10      9 71 25 64 38 52 5 31 19 45      16      26 35 17 92 53 24 6 57 21 12 34 2 17 86 75 33      20      15 87 32 7 84 35 26 45 78 96 52 22 37 65 9 43 21 3 33 91输出：No      Yes      No请教该如何实现？

Answer 1

1. 如果数字不大，比如最大的数字不超过100。可以建立一个大小为100的数组，初始化为0.比如array[100]

读入一个数字n之后，检查array[n]是否为0，不为表示之前出现过，返回true。否则继续遍历，并且把array[n]设为1.

类似于哈希。时间复杂度 o(n)

2. 如果数字很大，方法1不适合。可以先对所有数字排序，排序后有相同的数字必定相邻。遍历一遍检查相邻两个数有没有相同的即可。

排序复杂度比如堆排快排等是nlog(n)， 遍历是o(n) . 最后复杂度是 nlog(n)