元素去重

set

示例:

vector<int> nums = {1, 2, 3, 2, 1, 4, 5, 4, 6};

set<int> s(nums.begin(), nums.end());
nums.assign(s.begin(), s.end());

原理:

  1. set(集合)–每个元素只出现一次,且元素有序(默认升序).
  2. 将vector中的元素赋值给set,得到一个元素唯一的集合.
  3. 将set中的元素赋值给vector,得到一个元素唯一且有序的vector.

消耗:

  • 时间复杂度: O(n log n)
  • 空间复杂度: O(n)

二分查找

lower_bound()

示例:

vector<int> nums = {1, 3, 5, 7, 9};

int pos = lower_bound(nums.begin(), nums.end(), 5) - nums.begin();

cout << "The position of 5 is " << pos << endl; // 2

原理:

  1. lower_bound()返回指向第一个大于或等于给定值的元素的迭代器.
  2. 减去nums.begin()得到的位置,就能得到正确的索引.
  3. lower_bound()底层使用的是二分查找算法,因此如果数组无序,则结果不准确.

使用条件:

  1. 数组必须是有序的.

消耗:

  • 时间复杂度: O(log n)
  • 空间复杂度: O(1)