离散化处理 题目描述: 在程序设计过程中，经常要用到离散化处理，将原始数据排序，使用排序后的编号（rank值）作为新的关键字进行操作。排序后所有键值相同的数离散化处理后对应同一个编号。 输入格式: 第1行：一个整数N。 第2行：有N个整数，每个数在10^9以内。 输出格式: 依次输出每个数的rank编号。 样例输入: 4 28 5 6 5 样例输出: 3 1 2 1 提示: 1<=N<=100,000。 注意：可能有相同整数。 算法1提示： 1） 先sort； 2） 去重； 3） 二分查找每个值的位置。 算法2提示： 每个结构体元素中记录3项内容：（1）值，（2）原来的下标，（3）按值排序后的整理下标。 1）先按结构体中的值排序； 2）整理排序后的序号； 3）再按原始下标排序，排序后直接输出。 时间限制: 1000ms 空间限制: 128MB

以下是C++的算法1代码实现：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 1e5 + 5;

int a[N];
vector<int> s;

int find(int x)
{
    int l = 0, r = s.size()-1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(s[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l + 1;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    s.push_back(a[1]);
    for(int i = 2; i <= n; i++)
        if(a[i] != a[i-1]) s.push_back(a[i]);
    for(int i = 1; i <= n; i++)
        cout << find(a[i]) << " ";
    return 0;
}

思路：先对原始数据进行排序，去重后得到一个不重复的数组s。然后对于每个数，用二分查找在s中找到它的位置，即为rank值。

时间复杂度：排序的复杂度为O(nlogn)，去重的复杂度为O(n)，二分查找的复杂度为O(logn)，最终复杂度为O(nlogn)。

以下是C++的算法2代码实现：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 5;

struct node
{
    int val, id, rank;
}a[N];

bool cmp1(node x, node y)
{
    return x.val < y.val;
}

bool cmp2(node x, node y)
{
    return x.id < y.id;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i].val;
        a[i].id = i;
    }
    sort(a+1, a+n+1, cmp1);
    int cnt = 1;
    a[1].rank = cnt;
    for(int i = 2; i <= n; i++)
    {
        if(a[i].val != a[i-1].val) cnt++;
        a[i].rank = cnt;
    }
    sort(a+1, a+n+1, cmp2);
    for(int i = 1; i <= n; i++)
        cout << a[i].rank << " ";
    return 0;
}

思路：用结构体存储每个数的值、原始下标和rank值。先按值进行排序，然后整理出rank值。最后按原始下标排序，输出rank值。

时间复杂度：排序的复杂度为O(nlogn)，最终复杂度为O(nlogn)。