数据结构 结构体:离散化基础解题图路与题解代码

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

1. 离散化简介    离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率，通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小，    离散化本质上可以看成是一种哈希，其保证数据在哈希以后仍然保持原来的全/偏序关系，    当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来

1. 离散化简介

    离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。
    离散化本质上可以看成是一种哈希，其保证数据在哈希以后仍然保持原来的全/偏序关系。
    当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照从大到小编号来处理问题，即离散化。
    本文针对 整数、有序数组 进行离散化。

2.为什么要进行离散化处理？

    离散化是程序设计中一个常用的技巧，它可以有效的降低时间复杂度。
    其基本思想就是在众多可能的情况中，只考虑需要用的值。离散化可以改进一个低效的算法，甚至实现根本不可能实现的算法。

3. 举例说明

    有一个数组 a[] ，包含 1、3、100、2000、50000，五个数，将其对应映射到 0、1、2、3、4，的过程就叫做离散化。

4. 离散化过程中的问题

    数组 a[] 当中可能存在重复的元素，对此，我们需要 去重。
    如何算出 a[n] 离散化后的值，对此，我们可以使用 二分法 。具体见前文 整数二分

 

#include<bits/stdc++.h>
using namespace std;
struct sadbee__
{
    int sz,xh,px;
}a[10001];
bool sadbee(sadbee__ a,sadbee__ b)
{
    return a.sz<b.sz;
}
bool sadbee2(sadbee__ a,sadbee__ b)
{
    return a.xh<b.xh;
}
int main()
{
    int n,m,i,j;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i].sz;
        a[i].xh=i;
    }
    sort(a+1,a+n+1,sadbee);
    for(i=1;i<=n;i++)
    {
        a[i].px=i;
    }
    sort(a+1,a+n+1,sadbee2);
    for(i=1;i<=n;i++)
    {
        cout<<a[i].px<<" ";
    }
    return 0;
}

成为编程大师，不再是梦想！全网最全C++题库，助您开启编程新篇章。