如果我们只关心数据的相对位置,而不关心数据的具体数值,那么就要使用离散化处理来表示数据的位置。这种操作经常结合线段树等的数据结构,来压缩存储空间。直接看代码,很好理解。
#include <bits/stdc++.h> using namespace std; const int MAXN = 10; const int INF = 1000000; int num[MAXN]; // 存储数据 int a[MAXN], b[MAXN]; // a存储排名,b是num的副本 int main() { srand(time(unsigned(0))); // 随机数设置 cout << "number:" << endl; for(int i = 0; i < MAXN; ++i) { num[i] = rand() % INF; b[i] = num[i]; cout << num[i] << " "; } cout << endl; sort(num, num + MAXN); int n = distance(num, unique(num, num + MAXN)); // 离散化后元素的个数 cout << "n: " << n << endl; cout << "relative position::" << endl; for(int i = 0; i < MAXN; ++i) { a[i] = lower_bound(num, num + n, b[i]) - num + 1; // lower_bound返回迭代器,并计算位置 cout << a[i] << " "; } return 0; }几个STL说明: 1. distance(first, last)返回迭代器first和last的距离,可以自定义二元比较函数 2. unique(first, last)去除重复的连续元素,可以自定义二元比较函数。注意必须是有序序列的情况下,才能去除所有重复元素!!返回最后一个没有被移除的元素的后一个位置。有序序列的情况返回容器的last 3. lower_bound(first, last, val)返回有序序列中,第一个和val值相等的元素的地址,没有返回last,可以自定义二元比较函数。