数列离散化

· · 题解

题目解析

这段 C++ 代码解决的问题主要是对一系列整数进行离散化。离散化是一种常见的数据预处理方法，常用于处理具有明显区间特性的数据。离散化可以压缩数据的值域，使得处理更为便捷。

在这个问题中，给定一个整数数组，我们需要将数组中的所有数值离散化到从 1 开始的连续整数。

解题思路

  1. 读取并处理每个测试用例：对于每个测试用例，首先读入数组的长度 n，然后读入 n 个整数，存储到数组 a 中。同时，将数组 a 的内容复制到数组 b 中。 
    while(t--)
{
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i = 0;i < n;i++) cin >> a[i],b[i] = a[i];
    ...
  2. 排序并去重：对数组 b 进行排序，然后删除重复元素。这一步是离散化的关键步骤，它将所有不同的数值按照大小顺序排列。 
    sort(b.begin(),b.end());
b.erase(unique(b.begin(), b.end()),b.end());
  3. 进行离散化：遍历数组 a，使用 lower_bound 函数找到每个元素在数组 b 中的位置（由于数组 b 是排序过的，因此位置就相当于排名），然后将这个位置作为新的编号。由于数组下标从 0 开始，所以需要加 1 。 
    for(int i = 0;i < n;i++)
{
    a[i] = lower_bound(b.begin(),b.end(),a[i])-b.begin()+1;
    cout << a[i] << " ";
}

    在这个过程中，主要使用到了排序、二分查找和去重这几个算法。其中，sort 函数用于排序，unique 函数用于去重，lower_bound 函数用于二分查找。

这个代码的时间复杂度主要取决于排序和二分查找的复杂度，分别为 O(n \log n) 和 O(\log n)，所以总的时间复杂度为 O(n \log n)。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        vector<int> a(n), b(n);
        //复制到两个数组
        for(int i = 0;i < n;i++) cin >> a[i], b[i] = a[i];
        sort(b.begin(), b.end()); //对b数组排序
        b.erase(unique(b.begin(), b.end()), b.end()); //移除b中的重复元素
        //离散化处理：对a中的每个元素，查找其在b中的排序位置，并输出
        //这样可以将任何一组数据映射到一组连续的整数上，方便后续处理
        for(int i = 0;i < n;i++)
        {
            a[i] = lower_bound(b.begin(),b.end(),a[i])-b.begin()+1;
            cout << a[i] << " ";
        }
        cout << endl;
    }
    return 0;
}