【題目鏈接】
ybt 1245：不重復(fù)地輸出數(shù)
OpenJudge NOI 1.11 08:不重復(fù)地輸出數(shù)
【題目考點(diǎn)】
1. 二分查找
2. 復(fù)雜度為O(nlogn)的排序
- 快速排序：時間復(fù)雜度O(nlogn)，額外空間復(fù)雜度O(1)，不穩(wěn)定
- 歸并排序：時間復(fù)雜度O(nlogn)，額外空間復(fù)雜度O(n)，穩(wěn)定
【解題思路】
解法1：插入排序+二分查找
維護(hù)一個升序數(shù)組。
每讀入一個數(shù)字，先通過二分查找判斷數(shù)組中是否存在該數(shù)字。
- 如果存在，那么就略過。
- 如果不存在，就將該數(shù)字通過插入排序的方法插入到數(shù)組中，保持?jǐn)?shù)組是升序的。
最后輸出整個數(shù)組。
解法2：O(nlogn)排序算法
輸入數(shù)據(jù)的規(guī)模為10510^5105，可以使用復(fù)雜度為O(nlogn)的排序算法將其排序，然后遍歷數(shù)組，輸出時如遇到相同的元素，則只輸出一個。
【題解代碼】
解法1：插入排序+二分查找
#include<bits/stdc++.h>
using namespace std
;
#define N 100005
int a
[N
], an
;
bool isFound(int x
)
{int l
= 1, r
= an
, m
;while(l
<= r
){m
= (l
+ r
) / 2;if(x
< a
[m
])r
= m
- 1;else if(x
> a
[m
])l
= m
+ 1;elsereturn true;}return false;
}
int main()
{int n
, x
;cin
>> n
;for(int i
= 1; i
<= n
; i
++){cin
>> x
;if(isFound(x
) == false){a
[++an
] = x
;for(int j
= an
; j
> 1; j
--){if(a
[j
] < a
[j
-1])swap(a
[j
], a
[j
-1]);elsebreak; }}}for(int i
= 1; i
<= an
; ++i
)cout
<< a
[i
] << ' ';return 0;
}
- 使用stl函數(shù)：binary_search()
#include<bits/stdc++.h>
using namespace std
;
#define N 100005
int a
[N
], an
;
int main()
{int n
, x
;cin
>> n
;for(int i
= 1; i
<= n
; i
++){cin
>> x
;if(binary_search(a
+1, a
+1+an
, x
) == false){a
[++an
] = x
;for(int j
= an
; j
> 1; j
--){if(a
[j
] < a
[j
-1])swap(a
[j
], a
[j
-1]);elsebreak; }}}for(int i
= 1; i
<= an
; ++i
)cout
<< a
[i
] << ' ';return 0;
}
解法2：O(nlogn)排序
快速排序
#include<bits/stdc++.h>
using namespace std
;
#define N 100005
int a
[N
];
void qsort(int l
, int r
)
{int i
= l
, j
= r
, mid
= a
[(l
+r
)/2];while(i
<= j
){while(a
[i
] < mid
)i
++;while(a
[j
] > mid
)j
--;if(i
<= j
){swap(a
[i
], a
[j
]);i
++, j
--;}}if(l
< j
)qsort(l
, j
);if(i
< r
)qsort(i
, r
);
}
int main()
{int n
, x
;cin
>> n
;for(int i
= 1; i
<= n
; i
++)cin
>> a
[i
];qsort(1, n
);cout
<< a
[1] << ' ';for(int i
= 2; i
<= n
; ++i
)if(a
[i
] != a
[i
-1])cout
<< a
[i
] << ' ';return 0;
}
#include<bits/stdc++.h>
using namespace std
;
#define N 100005
int a
[N
];
int main()
{int n
, x
;cin
>> n
;for(int i
= 1; i
<= n
; i
++)cin
>> a
[i
];sort(a
+1, a
+1+n
);cout
<< a
[1] << ' ';for(int i
= 2; i
<= n
; ++i
)if(a
[i
] != a
[i
-1])cout
<< a
[i
] << ' ';return 0;
}
歸并排序
#include<bits/stdc++.h>
using namespace std
;
#define N 100005
int a
[N
], t
[N
];
void msort(int l
, int r
)
{if(l
>= r
)return;int m
= (l
+r
)/2;msort(l
, m
);msort(m
+1, r
);int ti
= l
, li
= l
, ri
= m
+1;while(li
<= m
&& ri
<= r
){if(a
[li
] < a
[ri
])t
[ti
++] = a
[li
++];elset
[ti
++] = a
[ri
++];}while(li
<= m
)t
[ti
++] = a
[li
++];while(ri
<= r
)t
[ti
++] = a
[ri
++];for(int i
= l
; i
<= r
; ++i
)a
[i
] = t
[i
];
}
int main()
{int n
, x
;cin
>> n
;for(int i
= 1; i
<= n
; i
++)cin
>> a
[i
];msort(1, n
);cout
<< a
[1] << ' ';for(int i
= 2; i
<= n
; ++i
)if(a
[i
] != a
[i
-1])cout
<< a
[i
] << ' ';return 0;
}
#include<bits/stdc++.h>
using namespace std
;
#define N 100005
int a
[N
];
int main()
{int n
, x
;cin
>> n
;for(int i
= 1; i
<= n
; i
++)cin
>> a
[i
];stable_sort(a
+1, a
+1+n
);cout
<< a
[1] << ' ';for(int i
= 2; i
<= n
; ++i
)if(a
[i
] != a
[i
-1])cout
<< a
[i
] << ' ';return 0;
}
總結(jié)
以上是生活随笔為你收集整理的信息学奥赛一本通 1245：不重复地输出数 | OpenJudge NOI 1.11 08:不重复地输出数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
