离散化

介绍

假如现在给你一堆数字，它们是无序的，可能相同的，且极差（$最大值-最小值$）很大，我们需要统计每个数出现的次数。

1. 当 $a_i \le 10^5$ 时，我们可以开一个桶，这个问题就变成了计数排序：
   CPP

   int const N = 1e5 + 7;
   int a[N], t[N];
   for(int i = 1; i <= n; i++){
   	cin >> a[i];
       t[a[i]]++;
   }
   

   这种做法虽然简单易写，但是处理不了大数据下的统计；
   那肯定有同学想到用哈希的做法，或者 STL 的 map 和 unordered_map;
2. 当 $a_i \le 10^{10},\, n \le 10^5$ 时，显然桶是不行了，因为元素很大，但是哈希可以啊：
   CPP

   unordered_map<int, int> hs;
   vector<int> v;
   for(int i = 1; i <= n; i++){
   	int a;
       cin >> a;
       hs[a] ++;
       v.push_back(a);
   }
   

   STL 提供的 unordered_map 为我们提供了 Hash表，简单且便于操作，可总是依赖 STL 不行，毕竟 它们的常数时间都很大，更不用说 list 了。
3. 当 $a_i \le 10^{10},\, n \le 10^5$ 时，除了哈希，我们还能用一种优化操作，离散化：
   建立一个离散数组，我们需要这些步骤
   1. 收集所有需要离散化的值
      我们随意列些值；
      CPP

      a[10] = {10, 7000, 42, 233, 233, 114514, 1919810, 1, -1000, -2718}
      

      这个数组里的元素，符合无序的，可能相同的，且极差很大；
      显然我们不能拿原数组进行离散化，因为还比较混乱；
   2. 排序
      将原数组排序结果复制在 $b$ 数组；
      CPP

      sort(a, a + 10);
      

      这时的数组 $b$ 变为，$a$ 数组不变：
      CPP

      [-2718, -1000, 1, 10, 42, 233, 233, 7000, 114514, 1919810];
      

      这时我们便可以看出数组的单调性。
   3. 去重
      离散数组不能有重复的元素，它更像 集合（set），
      这时的数组 $b$ :
      CPP

      [-2718, -1000, 1, 10, 42, 233, 7000, 114514, 1919810];
      

   4. 建立映射关系（从原始值到离散化后的索引）
      这里就是离散化最重要的一步，映射。
      CPP

      int t[N];
      for(int i = 0; i < n; i++) // pos为去重后数组的长度
      	t[i] = lower_bound(b, b + pos, a[i]) - b;
      

实践

原始数据: 10 7000 42 233 233 114514 1919810 1 -1000 -2718 

排序去重后: -2718 -1000 1 10 42 233 7000 114514 1919810 

离散化结果: 3 6 4 5 5 7 8 2 1 0 

映射关系:
原始值: -2718   -> 离散索引: 0
原始值: -1000   -> 离散索引: 1
原始值: 1       -> 离散索引: 2
原始值: 10      -> 离散索引: 3
原始值: 42      -> 离散索引: 4
原始值: 233     -> 离散索引: 5
原始值: 7000    -> 离散索引: 6
原始值: 114514  -> 离散索引: 7
原始值: 1919810 -> 离散索引: 8

#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int a[N], b[N], t[N]; // a:原始数组 b:排序数组 t:离散化结果
int n;                // 数据量

void discretize() {
    // 1. 复制到排序数组
    for(int i = 0; i < n; i++) b[i] = a[i];
    
    // 2. 排序
    sort(b, b + n);
    
    // 3. 去重 (返回去重后的尾地址)
    int pos = unique(b, b + n) - b;
    
    // 4. 建立映射
    for(int i = 0; i < n; i++) {
        t[i] = lower_bound(b, b + pos, a[i]) - b;
    }
    
    /* 输出示例
    printf("映射关系:\n");
    for(int i = 0; i < pos; i++) {
        printf("原始值 %d -> 离散值 %d\n", b[i], i);
    }
    */
}

适用场景对比

例题

洛谷 P1496 火烧赤壁

洛谷 P1955 程序自动分析