1.问题描述
考虑元素唯一性问题：给出一个整数集合，假定这些整数存储在数组A[1…n]中，确定它们中是否存在两个相等的元素。请设计出一个有效算法来解决这个问题，你的算法的时间复杂性是多少？
2. 具体要求
输入：输入的第一行是一个正整数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
4. 设计与实现的提示
算法最坏情况和平均情况的时间复杂性是衡量算法优劣的重要指标，算法设计要求尽可能设计比较高效的算法。
5、程序实现（java）
1
import java.io.*;
2public class Intrl1
3
{
4
public static void main(String[] args) throws Exception
5
{
6 Intrl1 intrl=new Intrl1();
7 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
8 System.out.println("请输入测试例个数:");
9 String str=br.readLine();
10 int m=Integer.parseInt(str);
11 intrl.Test(m);
12
}
13
14 public static int SPLIT(int[] A,int low,int high)
15 {
16 int w;
17 int i=low;
18 int x=A[low];
19 for(int j=low+1;j<=high;j++)
20 {
21 if(A[j]<=x)
22 {
23 i=i+1;
24
25 if(i!=j)
26 {
27 int a;
28 a=A[i];
29 A[i]=A[j];
30 A[j]=a;
31 }
32 }
33 }
34 int a2;
35 a2=A[low];
36 A[low]=A[i];
37 A[i]=a2;
38 w=i;
39 return w;
40 }
41
42 public static void quicksort(int[] A,int low,int high)
43 {
44 int w;
45 if(low<high)
46 {
47 w=SPLIT(A,low,high);
48 quicksort(A,low,w-1);
49 quicksort(A,w+1,high);
50 }
51 }
52 public static String check(int[]A)
53 {
54
55 String result="No";
56 if(A.length>1)
57 {
58 for(int i=0;i<A.length-1;i++)
59 {
60 if(A[i]==A[i+1])
61 {
62 return "Yes";
63 }
64 }
65 }
66 return result;
67 }
68 public void Test(int m)
69 {
70 String[] ss=new String[m];
71 for(int i=0;i<m;i++)
72 {
73 try
74 {
75
76 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
77 System.out.println("总测试例个数为"+m+",现请输入第"+(i+1)+"个用例数组的元素个数，并在下一行列出:");
78 String str=br.readLine();
79 int d=Integer.parseInt(str);
80 String str2=br.readLine();
81 String[] str3=str2.split(" ");
82 int[] ii=new int[d];
83 for(int j=0;j<d;j++)
84 {
85 ii[j]=Integer.parseInt(str3[j]);
86 }
87 quicksort(ii,0,d-1);
88 ss[i]=check(ii);
89 }
90 catch(IOException e)
91 {
92 System.out.println(e);
93 }
94 }
95 for(int i=0;i<m;i++)
96 {
97 System.out.println(ss[i]);
98 }
99 }
100
}
6、运行结果
