Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2133 Solved: 825
给出N个数,要求把其中重复的去掉,只保留第一次出现的数。
例如,给出的数为1 2 18 3 3 19 2 3 6 5 4,其中2和3有重复,去除后的结果为1 2 18 3 19 6 5 4。
输入第一行为正整数T,表示有T组数据。
接下来每组数据包括两行,第一行为正整数N,表示有N个数。第二行为要去重的N个正整数。
对于每组数据,输出一行,为去重后剩下的数字,数字之间用一个空格隔开。
2 11 1 2 18 3 3 19 2 3 6 5 4 6 1 2 3 4 5 6
1 2 18 3 19 6 5 4 1 2 3 4 5 6
对于30%的数据,1 <= N <= 100,给出的数不大于100,均为非负整数;
对于50%的数据,1 <= N <= 10000,给出的数不大于10000,均为非负整数;
对于100%的数据,1 <= N <= 50000,给出的数在32位有符号整数范围内。
提示:
由于数据量很大,使用C++的同学请使用scanf和printf来进行输入输出操作,以免浪费不必要的时间。
题解:在上一次A掉此题很久之后,我再一次看到了这个题= =
这次我用的是平衡树查询,简单的\( O\left(N\log N \right) \),而且速度貌似比上一次哈希还快
1 /**************************************************************
2 Problem: 2761
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:1840 ms
7 Memory:2180 kb
8 ****************************************************************/
9
10 var
11 i,j,k,l,m,n,head:longint;
12 a,b:array[0..100000] of longint;
13 lef,rig,fix:array[0..100000] of longint;
14 procedure rt(var x:longint);
15 var f,l:longint;
16 begin
17 if (x=0) or (lef[x]=0) then exit;
18 f:=x;l:=lef[x];
19 lef[f]:=rig[l];
20 rig[l]:=f;
21 x:=l;
22 end;
23 procedure lt(var x:longint);
24 var f,r:longint;
25 begin
26 if (x=0) or (rig[x]=0) then exit;
27 f:=x;r:=rig[x];
28 rig[f]:=lef[r];
29 lef[r]:=f;
30 x:=r;
31 end;
32 function ins(var x:longint;y:longint):boolean;
33 begin
34 ins:=true;
35 if x=0 then
36 begin
37 x:=y;
38 exit;
39 end;
40 if a[y]<a[x] then
41 begin
42 if lef[x]=0 then lef[x]:=y else ins:=ins(lef[x],y);
43 end
44 else if a[y]>a[x] then
45 begin
46 if rig[x]=0 then rig[x]:=y else ins:=ins(rig[x],y);
47 end
48 else exit(false);
49 end;
50 begin
51 readln(m);
52 randomize;
53 for l:=1 to m do
54 begin
55 readln(n);head:=0;
56 for i:=1 to n do
57 begin
58 read(a[i]);
59 lef[i]:=0;rig[i]:=0;
60 fix[i]:=random(maxlongint);
61 end;
62 readln;k:=0;
63 for i:=1 to n do
64 if ins(head,i) then
65 begin
66 inc(k);
67 b[k]:=a[i];
68 end;
69 for i:=1 to k do
70 if i<k then write(b[i],' ') else writeln(b[i]);
71 end;
72 readln;
73 end.