前言

对于一串数字序列(或者一个平面)，我们要得到其中每个位置得相对位置，但这段数字可能存在间隔十分大，从而产生类似于稀疏矩阵这样浪费空间的问题(这个形容可能不恰当)，比如我们要对这段序列进行桶排序类似物的处理。这是我们可以对其进行求出相对位置（也可以理解为这个数字在这段序列中的排名），而不是原本的绝对位置，利用离散化可以解决这样的问题。

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：
原数据：1,999,100000,15；处理后：1,3,4,2；
原数据：{100,200}，{20,50000}，{1,400}；
处理后：{3,4}，{2,6}，{1,5}；

摘自百度百科

离散化

方法一，

适用于所有情况(sort + unique + lower_bound)三段式：
1，将数据集arr1的内容复制到arr2中，并排序
2，利用unique将arr2中去重(前提有序，已做)
3，利用lower_bound函数查询arr1每个数字的排名

方法二，

只适用于无重复的情况:
1，定义一个类中排序前的位置以及值得两个成员变量
2，根据值排序
3，根据排序前得位置(成员变量idx)赋值当前排序后得排名

测试代码

#include <iostream>
#include <algorithm>

using namespace std;
const int maxn = (int)1e4+5;

//方法1
int arr1[maxn],arr2[maxn],rank1[maxn];
void solve_1 (int n) {
	
	cout << "============方法1处理结果============\n" << '\n';
	
	for (int i = 1; i <= n; i++) {
		cin >> arr1[i];
		arr2[i] = arr1[i];
	}
	sort(arr2 + 1, arr2 + 1 + n); // 有序
	
	int len = unique(arr2 + 1, arr2 + 1 + n) - arr2 - 1; // 去重
	cout << "len = " << len << '\n';

	for(int i = 1; i <= n; i++) {
		rank1[i] = lower_bound(arr2 + 1, arr2 + 1 + len, arr1[i]) - arr2;
	}

	cout << "rank:" << '\n';
	for (int i = 1; i <= n; i++) {
		cout << "val = " << arr1[i] << " rank = " << rank1[i] << '\n';
	}
	cout << "=====================================\n" << '\n';
}

//方法2
struct Node {
	int val,idx;
	bool operator < (const Node& A) const {
		if(val < A.val) {
			return true;
		}
		return false;
	}
};

int rank2[maxn],tmp[maxn]; Node arr3[maxn];
void solve_2 (int n) {
	cout << "============方法2处理结果============\n" << '\n';

	for (int i = 1; i <= n; i++) {
		cin >> arr3[i].val;
		arr3[i].idx = i;
		tmp[i] = arr3[i].val;
	}
	sort(arr3 + 1, arr3 + 1 + n); // 有序

	for(int i = 1; i <= n; i++) {
		rank2[arr3[i].idx] = i;
	}

	cout << "rank:" << '\n';
	for (int i = 1; i <= n; i++) {
		cout << "val = " << tmp[i] << " rank = " << rank2[i] << '\n';
	}
	cout << "=====================================\n" << '\n';
}



int main() {
	solve_1(6);  //重复 input:6 1000 2001 7 1000 305
	solve_1(6);  //非重复 input:6 1000 2001 7 10001 560
	solve_2(6);  //非重复 input:6 1000 2001 7 10001 560
	return 0;
}