c++算法之离散化

目录

离散化

实现方法

例题

离散化

把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

离散化是一种将数组的值域压缩，从而更加关注元素的大小关系的算法。

当原数组中的数字很大、负数、小数时(大多数情况下是数字很大)，难以将“元素值”表示为“数组下标”，一些依靠下标实现的算法和数据结构无法实现时，我们就可以考虑将其离散化。

例如原数组的范围是[1,1e9]，而数组大小仅为1e5，那么说明元素值的“种类数”最多也就1e5种，从而可以利用一个数组(即离散化数组)来表示某个元素值的排名(即第几小)现值域的压缩，将原数组的元素值作为下标来处理。

实现方法

#include <iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>L;//离散化数组

//返回x在L中的下标
int getidx(int x)
{
	return lower_bound(L.begin(), L.end(), x) - L.begin();
}

const int N = 1e5 + 9;

int a[N];

int main()
{
	int n; cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}
	//将元素存入L数组中
	for (int i = 1; i <= n; i++)L.push_back(a[i]);

	//排序去重
	L.erase(unique(L.begin(), L.end()), L.end());

	return 0;
}

例题

给定a数组，求a的离散化数组，并可以通过值找到下标

#include <iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1e5 + 9;
int a[N];
vector<int>L;//离散化数组

//返回x在L中的下标
int getidx(int x)
{
	return lower_bound(L.begin(), L.end(), x) - L.begin();
}


int main()
{
	int n; cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}
	//将元素存入L数组中
	for (int i = 1; i <= n; i++)L.push_back(a[i]);
	sort(L.begin(), L.end());
	//排序去重
	L.erase(unique(L.begin(), L.end()), L.end());

	cout << "离散化数组为：";
	for (const auto& i : L)cout << i << ' ';
	cout << endl;

	int val; cin >> val;

	cout << getidx(val) << endl;

	return 0;
}

结果：

5
2 3 3 1 4
离散化数组为：1 2 3 4
3
2