背景引入

對于一個數字序列，如果我們只關心他們之間的相對大小，而不關心具體數值，并且直接使用原數值會對我們的解決方案產生影響，此時我們采用離散化

具體步驟

即將一個原數組映射到另一個等大的數組中，并且兩個數組數字之間的大小關系不變
如：原序列= [ 12 4 80 7 6 11 4 5*10e10] 可以映射成： [5 1 6 3 2 4 1 7]

代碼詳解

#include <algorithm>
#include <iostream>
using namespace std;
bool cmp(int a, int b) {
	return a < b;
}
int main() {
	int n = 8;
	int arr[] = {12, 4, 80, 7, 6, 11, 4, int(5 * 10e10)};
	int sorted[n];
	copy(arr, arr + n, sorted);
	sort(sorted, sorted + n, cmp);
	for (int i = 0; i < n; i++) {
		arr[i] = lower_bound(sorted, sorted + n, arr[i]) - sorted + 1;
	}
	return 0;
}

解釋

在上述代碼中，我們先構建了一個原數組的排序，即sorted = [4 4 6 7 11 12 80 5*10e10]
通過代碼

for (int i = 0; i < n; i++) {
		arr[i] = lower_bound(sorted, sorted + n, arr[i]) - sorted + 1;
	}

我們先獲得的arr[i]在sorted中的第一個不大于它的迭代器（指針），比如對于arr[i]=7，先返回指向sorted中的7的指針，減去sorted就會得到7在sorted中的位置n，即*(sorted+n) = 7，再加一就得到是第幾個數字，這樣就可以把原數組映射到一個連續且等于其長度的數組中了