离散化

大家好，欢迎来到IT知识分享网。

理解

离散化本质上是一种特殊的哈希，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
简单来说，就是在不改变数据的相对大小的情况下，对数据进行一定的缩小。
例如

还有

以上数据很容易发现离散化的用途，当你所需要的数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。
若不离散化，则针对该例需要开一个大小很大的数组保存操作结果；

大致流程

1.通过建立一个映射数组来存储所有要进行操作的下标X，然后将其排序去重，每次操作X位置元素时用二分法查找X在映射数组中的位置Y。操作X位置元素改为操作Y位置元素。
2.排序是为了方便二分查找，排序后去重比较方便；
3.去重是为了建立X与Y的一一映射，不去重则会导致一个X可以对应多个Y（可以不去重，每次查询X只返回特定的Y就行了，但是这样时间复杂度更慢，所以最好还是去重）。
4.离散化也有缺点，就是它排序去重需要nlogn的时间，每次操作要用logn倍直接操作的时间

基本代码模板

#include<bits/stdc++.h>
using namespace std;
//a为原数组，mem为映射数组
int n, a[100000], mem[100000];
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
                //mem是一个临时数组，用来得到离散化的映射关系
		mem[i] = a[i];
	}
        //排序
	sort(mem, mem + n);
        //去重，并获得去重后的长度sz
	int sz = unique(mem, mem + n) - mem;
	for (int i = 0; i < n; i++)
	{
		a[i] = lower_bound(mem, mem + sz, a[i]) - mem;
		cout << a[i] << ' ';
	}

	return 0;
}

离散化_应用场景

例题链接：https://www.acwing.com/problem/content/description/105/

题意
有 n 个科学家，每个科学家都只懂得一种语言，所以把世界上的所有语言用整数编号。
一共有 m 部电影，每部电影的语音和字幕都采用不同的语言。
如果能听懂电影的语音，很开心；如果能看懂字幕，比较开心；如果全都不懂，就会不开心。
现在看同一场电影。
请你帮忙选择一部电影，可以让观影很开心的人最多。
如果有多部电影满足条件，则在这些电影中挑选观影比较开心的人最多的那一部。
思路
有两种思路，一种是用map,好用又好做;
先上STL;

// 定义一个map对象,前key后value;
map<int, string> m;

//------插入-------
//用insert函数插入pair
m.insert(pair<int, string>(420, "avicii"));

// 用insert函数插入value_type数据
m.insert(map<int, string>::value_type(420, "avicii"));
 
// 用数组方式插入
m[420] = "avicii";

//-------查找-------
map<string,int>::iterator it;
it=m.find("avicii");

//-------删除-------
//迭代器刪除
it = m.find("avicii");
m.erase(it);

//关键字删除
int n = m.erase("avicii"); //如果刪除了返回1，否则返回0

//用迭代器范围刪除 : 把整个map清空
m.erase(m.begin(), m.end());

//-------长度-------
int len = m.size();//获取到map中映射的次数

//-------遍历-------
map< string, int>::iterator it;
for (it = m.begin(); it != m.end(); it++)
{
	cout << it->first << " " << it->second << endl;//输出key 和value值
}

//maps.empty()判断其是否为空
//maps.swap()交换两个map

另一种就是离散化做法，因为离散化本身就是一种特殊的哈希，所以离散化在本题反而显得复杂，多此一举

题解代码

//-------map做法-------
#include<bits/stdc++.h>
#define N 200010
using namespace std;
map<int,int>s;//s[i] = t表示使用i语言的科学家有t个
int a[N];
int b[N];
int n,m,i,j,k;
struct movie//电影的属性
{
    int a;
    int b;
}p[N];
int main()
{
    cin >> n;
    for(i=0;i<n;i++)
    {
        cin >> a[i];
        s[a[i]]++;
    }
    cin >> m;
    for(i=1;i<=m;i++)
        cin >> p[i].a;
    for(i=1;i<=m;i++)
        cin >> p[i].b;

    int x = 0;
    k=1;
    for(i=1;i<=m;i++)
    {
        //找到出现科学家最多的语音的电影,统计科学家个数并记录其在电影列表中第一次出现的位置
        if(x < s[p[i].a])
        {
            x = s[p[i].a];
            k=i;
        }
    }


    int num = 0;
    for(i=1;i<=m;i++)
    {
        //在科学家语音个数相等的情况下，比较字幕。记录出现科学家最多的字幕最大的电影位置
        if(s[p[i].a]==x)
        {
            if(num<s[p[i].b])
            {
                num=s[p[i].b];
                k=i;
            }
        }
    }

    cout << k << endl;
    return 0;
} 

//-------离散化-------
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=2e5+5;
int n,m;
int a[maxn],b[maxn],c[maxn];
int sum[maxn*3];
int cnt,mm;
int arr[maxn*3],num[maxn*3];
//离散化
void discrete()
{
    sort(arr+1,arr+cnt+1);
    for(int i=1;i<=cnt;i++)
    {
        if(i==1||arr[i]!=arr[i-1])
            num[++mm]=arr[i];
    }
}
//二分查找x的位置
int query(int x)
{
    return lower_bound(num+1,num+mm+1,x)-num;
}
int main()
{
    cin >> n;
    //将所有电影和人涉及的语言放进一个数组，排序并离散化
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        arr[++cnt]=a[i];
    }
    cin >> m;
    for(int i=1;i<=m;i++)
    {
        cin >> b[i];
        arr[++cnt]=b[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin >> c[i];
        arr[++cnt]=c[i];
    }
    discrete();//离散化

    //sum数组类似于map使用，统计n序列中数字的出现个数
    //所以这样看来，还不如直接用map，不用扯什么排序和离散化
    for(int i=1;i<=n;i++)
    {
        int num = query(a[i]);//统计每种语言的人的数量
        ++sum[num];
    }
    int bmax=-1,cmax=-1,ans=0;
    //选择满足题目要求的电影
    for(int i=1;i<=m;i++)
    {
        int x=query(b[i]);
        int y=query(c[i]);
        //优先考虑语音最多
        if(sum[x]>bmax)
        {
            bmax=sum[x],cmax=sum[y];
            ans=i;
        }
        else 
        {
            //如果答案不唯一、则在此前提下再比字幕最多
            if(sum[x]==bmax&&sum[y]>cmax)
            {
                bmax=sum[x],cmax=sum[y];
                ans=i;
            }
        }
    }
    cout << ans << endl;
    return 0;
}