查看“︁04-数据结构/07-STL实用例子”︁的源代码


== 明明的随机数 ==

排序 + 去重。

=== 使用 <code>sort</code> + <code>unique</code> ===

<syntaxhighlight lang="cpp">
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    int nn = unique(a.begin(), a.end()) - a.begin();
    cout << nn << "\n";
    for (int i = 0; i < nn; i++)
        cout << a[i] << " ";
    return 0;
}
</syntaxhighlight>

=== 计数排序 ===

<syntaxhighlight lang="cpp">
const int MAXAI = 1000;
int cnt[MAXAI + 5];

int main()
{
    int n, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        cnt[x]++;
        if (cnt[x] == 1)
            ans++;
    }
    cout << ans << "\n";
    for (int i = 1; i <= MAXAI; i++)
        if (cnt[i] >= 1)
            cout << i << " ";
}
</syntaxhighlight>

=== bitset ===

<syntaxhighlight lang="cpp">
const int MAXAI = 1000;
bitset<MAXAI + 1> cnt;

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        cnt.set(x);
    }
    cout << cnt.count() << "\n";
    for (int i = 1; i <= MAXAI; i++)
        if (cnt[i])
            cout << i << " ";
}
</syntaxhighlight>

== 合并果子（priority_queue） ==

<syntaxhighlight lang="cpp">
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        pq.push(x);
    }
    long long ans = 0;
    while (pq.size() > 1)
    {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        ans += a + b;
        pq.push(a + b);
    }
    cout << ans;
    return 0;
}
</syntaxhighlight>

== 全排列（<code>next_permutation</code>） ==

<syntaxhighlight lang="cpp">
int n;
int a[10];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        a[i] = i;
    do
    {
        for (int i = 1; i <= n; i++)
            cout << "    " << a[i];
        cout << "\n";
    } while (next_permutation(a + 1, a + n + 1));
    return 0;
}
</syntaxhighlight>

== 求第 k 大数（<code>nth_element</code>） ==

时间复杂度 <math>O(n)</math>。

<syntaxhighlight lang="cpp">
int n, k;
int a[1000005];

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    nth_element(a + 1, a + k, a + n + 1, greater<int>());
    cout << a[k];
    return 0;
}
</syntaxhighlight>

== STL 算法速查 ==

{| class="wikitable"
! 算法 !! 说明
|-
| <code>sort(begin, end)</code>
| 排序
|-
| <code>sort(begin, end, cmp)</code>
| 自定义排序
|-
| <code>stable_sort(begin, end)</code>
| 稳定排序
|-
| <code>unique(begin, end)</code>
| 去重（需先排序）
|-
| <code>lower_bound(begin, end, x)</code>
| 第一个 <math>\ge x</math> 的位置
|-
| <code>upper_bound(begin, end, x)</code>
| 第一个 <math>> x</math> 的位置
|-
| <code>binary_search(begin, end, x)</code>
| 二分查找是否存在
|-
| <code>next_permutation(begin, end)</code>
| 下一个排列
|-
| <code>reverse(begin, end)</code>
| 反转
|-
| <code>max_element(begin, end)</code>
| 最大值位置
|-
| <code>min_element(begin, end)</code>
| 最小值位置
|-
| <code>count(begin, end, x)</code>
| 统计出现次数
|-
| <code>fill(begin, end, x)</code>
| 填充
|-
| <code>nth_element(begin, nth, end)</code>
| 找第 k 大
|}

> 所有区间均为'''左闭右开''' <code>[begin, end)</code>


[[Category:数据结构]]
[[Category:三三文档]]