117笔记问答在C++中，set是一个关联容器，它包含一组唯一的元素，并按照特定的排序规则进行存储。set在算法设计中的应用主要体现在以下几个方面：
- 去重：由于
set中的元素都是唯一的，因此可以使用set来实现去重操作。将一个容器中的元素插入到set中，然后再从set中取出元素，这样就可以得到一个去重后的序列。
#include#include #include using namespace std; int main() { vector nums = {1, 2, 3, 4, 4, 5, 6, 6, 7}; set s(nums.begin(), nums.end()); for (int num : s) { cout<< num << " "; } return 0; }
- 查找：
set提供了高效的查找操作，可以在O(log n)的时间复杂度内完成查找。如果需要在一个有序的序列中查找某个元素，可以使用set来实现。
#include#include using namespace std; int main() { set s = {1, 2, 3, 4, 5, 6, 7}; int target = 4; if (s.find(target) != s.end()) { cout << "Found "<< target<< endl; } else { cout << "Not found"<< endl; } return 0; }
- 区间查询：
set还支持区间查询，可以在O(log n)的时间复杂度内找到某个区间内的所有元素。例如，可以使用lower_bound和upper_bound函数来查找一个区间内的所有元素。
#include#include using namespace std; int main() { set s = {1, 2, 3, 4, 5, 6, 7}; int lower = 3, upper = 6; auto it_low = s.lower_bound(lower); auto it_up = s.upper_bound(upper); for (auto it = it_low; it != it_up; ++it) { cout << *it << " "; } return 0; }
- 最大/最小值：
set中的第一个元素是最小值，最后一个元素是最大值。可以通过*s.begin()和*s.rbegin()来获取最小值和最大值。
#include#include using namespace std; int main() { set s = {1, 2, 3, 4, 5, 6, 7}; cout << "Min: " << *s.begin()<< endl; cout << "Max: " << *s.rbegin()<< endl; return 0; }
- 排序：
set会自动对其中的元素进行排序。如果需要对一个序列进行排序，可以将其插入到set中，然后再从set中取出元素，这样就可以得到一个有序的序列。
#include#include #include using namespace std; int main() { vector nums = {7, 3, 1, 6, 4, 2, 5}; set s(nums.begin(), nums.end()); for (int num : s) { cout<< num << " "; } return 0; }
总之，set在算法设计中的应用非常广泛，可以帮助我们实现去重、查找、区间查询、最大/最小值查询和排序等功能。