一维离散化笔记

一维离散化笔记

通俗来说，一维离散化就是把在无限空间中的有限元素映射到一个线性排列的区间中

举个实际的例子说明：

存在一个近似无限的空间 \([-10^9,10^9]\) ，我们需要对其中\(10^5\)个离散的元素进行操作

显然不可能对这个近似无限的区间进行\(10^5\)次遍历

所以需要把这\(10^5\)个元素映射到一个数组内

相当于缩短元素与元素之间的距离，减少遍历复杂度

这里有一个例题来具体实现这个算法：

给定一个长度为 n 的数组a，定义 rank(i) 表示数组a 中比 a_i 小的不同数字个数再加 1

输入：

输入的第一行是一个整数，表示数据组数 T，接下来依次给出每组数据的信息：

第一行是一个整数，表示数列长度 n
第二行有 n个整数表示数列 a，第 i 个整数表示 a_i

输出：

对每组数据，输出一行 n个整数，用空格隔开，依次表示 rank(1)到 rank(n)

备注：

\(1<=T<=5\), \(1<=n<=10^5\), \(-10^9<=a_i<=10^9\)

首先需要将输入的 a_i 映射进一个数组，可以使用vector来进行这一步操作

vector<int> a,b;
int temp;
for (int i=0;i<n;i++) {
	cin>>temp;
	a.push_back(temp);
	b.push_back(temp);
}

同时需要拷贝一次 a 数组，便于进行后面的操作

然后我们对 a 数组进行排序和去重操作：

sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());

这里解释一下unique函数的作用：

iterator unique(iterator it_1,iterator it_2,bool MyFunc);

第一个参数为需要去重的区间的首个元素的迭代器，第二个参数为需要去重的区间的末尾元素的迭代器

然后将重复的元素移动到数组的末尾，重复操作直到迭代器移动到指定的末尾元素

返回的是不重复元素的下一个元素的迭代器

再使用erase函数擦除由unique函数返回的指向重复元素的迭代器与指向排序后的 a 数组末尾元素的迭代器之间的所有元素

就可以得到排序去重后的 a 数组

接下来是计算 rank(i) 的操作：该如何查找比 b_i 小的不重复元素？

使用lower_bound函数可以精简的完成这个过程：

ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,  const T& val);

函数的第一个参数为需要查找的区间的首个元素的迭代器，第二个参数为需要查找的区间的末尾元素的迭代器

第三个参数为需要查找的值

b[i] = lower_bound(a.begin(), a.end(), b[i]) - a.begin()+1;

解释这步操作：

b数组存储的是原始排列，a数组存储的是排序去重后的排列

使用lower_bound在 a数组中查找到 b_i 的迭代器，再减去 a数组首个元素的迭代器得到 b_i 前不重复元素的个数即rank(i)

将这个值再次赋值给 b_i （节约空间），最后输出 b数组的所有元素即可AC

完整代码：

int main()
{
	int T,n,temp;
	cin >> T;
	for (int t = 0; t < T; t++) {
		vector<int> a,b;
		int temp = 0;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> temp;
			b.push_back(temp);
			a.push_back(temp);
		}
		sort(a.begin(), a.end());
		a.erase(unique(a.begin(), a.end()), a.end());
		for (int i = 0; i < n; i++) {
			b[i] = lower_bound(a.begin(), a.end(), b[i]) - a.begin()+1;
		}
		for (int i = 0; i < n; i++) cout << b[i] << " ";
		cout << endl;
	}
	return 0;
}