简介

可以理解为一种可以保持大小顺序的哈希，是一种优化技巧。

相同元素用相同数字:

int n;
std::vector<int> arr(n), tmp(n);
// 创建副本
for(int i = 0; i < n; ++i) 
  tmp[i] = arr[i];
// 排序
std::sort(tmp.begin(), tmp.end());
// 去重
int len = std::unique(tmp.begin(), tmp.end()) - tmp.begin();
// 二分查找结果
for(int i = 0; i < n; ++i) 
  arr[i] = std::lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin();

相同元素用不同数字:

int n;
std::vector<int> arr(n);
std::vector<std::pair<int, int>> tmp(n);
// 创建副本
for(int i = 0; i < n; ++i) 
  tmp[i] = {arr[i], i};
// 排序
std::sort(tmp.begin(), tmp.end());
// 直接回馈结果
for(int i = 0; i < n; ++i) 
  arr[tmp[i].second] = i;