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")