跳转至

離散化

簡介

離散化是一種數據處理的技巧，本質上可以看成是一種 哈希，其保證數據在哈希以後仍然保持原來的 全/偏序 關係。

通俗地講就是當有些數據因為本身很大或者類型不支持，自身無法作為數組的下標來方便地處理，而影響最終結果的只有元素之間的相對大小關係時，我們可以將原來的數據按照排名來處理問題，即離散化。

用來離散化的可以是大整數、浮點數、字符串等等。

實現

將一個數組離散化，並進行查詢是比較常用的應用場景。

方法一

通常原數組中會有重複的元素，一般把相同的元素離散化為相同的數據。

方法如下：

  1. 創建原數組的副本。

  2. 將副本中的值從小到大排序。

  3. 將排序好的副本去重。

  4. 查找原數組的每一個元素在副本中的位置，位置即為排名，將其作為離散化後的值。

1
2
3
4
5
6
7
8
// arr[i] 為初始數組,下標範圍為 [1, n]

for (int i = 1; i <= n; ++i)  // step 1
  tmp[i] = arr[i];
std::sort(tmp + 1, tmp + n + 1);                          // step 2
int len = std::unique(tmp + 1, tmp + n + 1) - (tmp + 1);  // step 3
for (int i = 1; i <= n; ++i)                              // step 4
  arr[i] = std::lower_bound(tmp + 1, tmp + len + 1, arr[i]) - tmp;

參考實現中使用的 STL 算法可參考 STL 算法。

同樣地，我們也可以對 std::vector 進行離散化：

1
2
3
4
5
6
// std::vector<int> arr;
std::vector<int> tmp(arr);  // tmp 是 arr 的一個副本
std::sort(tmp.begin(), tmp.end());
tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
for (int i = 0; i < n; ++i)
  arr[i] = std::lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin();

方法二

根據題目要求，有時候會把相同的元素跟據輸入順序離散化為不同的數據。

此時再用 std::lower_bound() 函數實現就有些困難了，需要換一種思路：

  1. 創建原數組的副本，同時記錄每個元素出現的位置。

  2. 將副本按值從小到大排序，當值相同時，按出現順序從小到大排序。

  3. 將離散化後的數字放回原數組。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
struct Data {
  int idx, val;

  bool operator<(const Data& o) const {
    if (val == o.val)
      return idx < o.idx;  // 當值相同時，先出現的元素離散化後的值更小
    return val < o.val;
  }
} tmp[maxn];  // 也可以使用 std::pair

for (int i = 1; i <= n; ++i) tmp[i] = (Data){i, arr[i]};
std::sort(tmp + 1, tmp + n + 1);
for (int i = 1; i <= n; ++i) arr[tmp[i].idx] = i;

複雜度

對於方法一，去重複雜度為 \(O(n)\)，排序複雜度為 \(O(n \log n)\)，最後的 \(n\) 次查找複雜度為 \(O(n \log n)\)。

對於方法二，排序複雜度為 \(O(n \log n)\)。

故兩種方法的總時間複雜度都為 \(O(n \log n)\)。

空間複雜度為 \(O(n)\)。

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：GavinZhengOI, PlanariaIce
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用