HJ3 明明的随机数【牛客网】

零、原题链接

HJ3 明明的随机数

一、题目描述

二、测试用例

三、解题思路

3.1 快排+去重

1. 基本思路：
     先将序列进行快速排序，然后将重复的数字删除。
2. 具体思路：
   • 将序列排序；
   • 遍历序列，每次遍历到新的元素，打个标记，后续遍历时，如果遍历到的元素与标记元素不相同，则更新标记且输出该元素。

3.2 散列

1. 基本思路：
     将序列的元素按照元素本身进行散列，然后按照顺序进行输出即可。
2. 具体思路：
   • 将序列排序；
   • 遍历序列，每次遍历到新的元素，打个标记，后续遍历时，如果遍历到的元素与标记元素不相同，则更新标记且输出该元素。

四、参考代码

4.1 快排+去重

时间复杂度：$\mathrm{O}(nlogn)$【快排的复杂度】
空间复杂度：$\mathrm{O}(n)$

#include <functional>
#include <iostream>
#include <vector>
using namespace std;int main() {int n;cin >> n;vector<int> ans(n);for (int i = 0; i < n; i++) {cin >> ans[i];}sort(ans.begin(), ans.end(), less<int>());int i = 0;cout << ans[0] << endl;for (int j = 1; j < n; j++) {if (ans[i] != ans[j]) {i = j;cout << ans[i] << endl;}}
}
// 64 位输出请用 printf("%lld")

4.2 散列

时间复杂度：$\mathrm{O}(n)$【散列元素的复杂度】
空间复杂度：$\mathrm{O}(1)$【散列表的空间为常数级】

#include <functional>
#include <iostream>
#include <vector>
using namespace std;int main() {const int max = 501;int n;cin >> n;vector<bool> m(max);int t;for (int i = 0; i < n; i++) {cin >> t;m[t] = true;}for (int i = 0; i < max; i++) {if (m[i])cout << i << endl;}
}
// 64 位输出请用 printf("%lld")