STL 算法

概念讲解

常用算法

算法 说明 时间复杂度
sort 排序 O(n log n)
lower_bound 下界 O(log n)
upper_bound 上界 O(log n)
unique 去重 O(n)
next_permutation 下一个排列 O(n)
nth_element 第 n 小 O(n)
reverse 翻转 O(n)
find 查找 O(n)

sort

1234567891011#include <algorithm>

int a[] = {3, 1, 4, 1, 5};
sort(a, a + 5);  // 升序
sort(a, a + 5, greater<int>());  // 降序

// 自定义比较
bool cmp(int a, int b) {
    return a > b;
}
sort(a, a + n, cmp);

lower_bound / upper_bound

12345678910// 在有序数组中查找
int a[] = {1, 2, 3, 3, 3, 4, 5};

// 第一个 >= 3 的位置
int* it = lower_bound(a, a + 7, 3);
int pos = it - a;  // 2

// 第一个 > 3 的位置
int* it = upper_bound(a, a + 7, 3);
int pos = it - a;  // 5

next_permutation

12345int a[] = {1, 2, 3};
do {
    for (int i = 0; i < 3; i++) cout << a[i] << " ";
    cout << endl;
} while (next_permutation(a, a + 3));

nth_element

123int a[] = {3, 1, 4, 1, 5, 9, 2, 6};
nth_element(a, a + 3, a + 8);  // 第 4 小的元素在正确位置
// a[3] = 3

考点分析

初赛考查方式

  1. 程序阅读： STL 算法
  2. 编程题： 算法应用

常见考点

  • sort 自定义比较
  • lower_bound/upper_bound
  • next_permutation

例题精讲

例题 1：lower_bound

题目： 在 {1,3,3,5,7} 中找第一个 >= 3 的位置。

解答：

位置是 1（下标从 0 开始）。

例题 2：去重

题目： 对数组去重。

解答：

12sort(a, a + n);
int len = unique(a, a + n) - a;

练习题

  1. lower_bound 和 upper_bound 的区别？
查看答案
函数 说明 示例（数组 {1,3,3,3,5}）
lower_bound 第一个 >= target 的位置 lower_bound(3) = 位置 1
upper_bound 第一个 > target 的位置 upper_bound(3) = 位置 4

两者都要求数组有序。

  1. 如何用 next_permutation 生成全排列？
查看答案
1234567#include <algorithm>

int a[] = {1, 2, 3};
do {
    for (int i = 0; i < 3; i++) cout << a[i] << " ";
    cout << endl;
} while (next_permutation(a, a + 3));

注意：使用前要先排序，否则会漏掉排列。

  1. nth_element 的时间复杂度是多少？
查看答案

O(n)（平均）

nth_element 会将第 n 小的元素放到正确位置，但不保证其他元素有序。

123int a[] = {3, 1, 4, 1, 5, 9, 2, 6};
nth_element(a, a + 3, a + 8);
// a[3] 是第 4 小的元素

易错点

⚠️ 注意：

  1. lower_bound/upper_bound 要求数组有序
  2. next_permutation 使用前要排序
  3. unique 只去除相邻重复元素
  4. nth_element 不保证完全排序