c++離散化處理大範圍和重複資料

c++離散化處理大範圍和重複資料

關于離散化

有些新手可能會問：離散化是什麼？離散化就是将無限空間中有限的個體映射到有限的空間裡去。

上面的定義肯定會有人看不懂（其實我剛開始學的時候也看不懂）

用我自己的話來說，就是在不改變資料的相對大小的條件下，對資料進行相應的壓縮

可能還是有人看不懂，沒關系，我們來看一個例子，順便來講一下離散化的基本操作：

現有一個數組：1，100，2367，562，364737，19，1974832947，100，562，2367

如果按照正常的方法，該開1974832947的空間，但是經過離散化後，就不需要

那麼step 1：排序

用上面的例子來說，就是将上面的資料排序并去重，得到下面這組資料：

1，19，100，100，562，562，2367，2367，364737，1974832947

然後step 2：通過unique去重使大小與下标對應，并得到去重後的長度，得到下面這組資料：

1，19，100，562，2367，364737，1974832947

接着step 3：通過lower_bound算出離散化後的排列，得到下面這組資料：

1，2，3，4，5，6，7

那麼這裡就很尴尬了，這組資料無法應用于初始資料

是以在開始，我們多定義1個數組，來記錄初始情況下的資料，再用step 3與其進行對應。

最終得到答案：1，3，5，4，6，2，7，3，4，5

下面給出模闆：

 View Code

原文位址

https://www.cnblogs.com/jasonownblog/p/12906712.html