My code for coordinate compression

Правка en2, от rembocoder, 2020-10-29 03:42:57

Hi. I want to share a simple method for coordinate compression. Even noob can write it.

vector<int> a(n);
// read the vector
vector<int> b = a;
sort(b.begin(), b.end());
map<int, int> m;
for (int i = 0; i < n; i++) {
    m[b[i]] = i;
}
for (int i = 0; i < n; i++) {
    a[i] = m[a[i]];
}

Now every value of an array lies in [0, n). The most convineint it that if you need the original value for a[i], you can just write b[a[i]].

And how do you write it?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru3 Русский rembocoder 2020-10-29 03:43:39 2 Мелкая правка: ' {\n m[a[i]] = i;\' -> ' {\n m[b[i]] = i;\'
en2 Английский rembocoder 2020-10-29 03:42:57 2 Tiny change: ' {\n m[a[i]] = i;\' -> ' {\n m[b[i]] = i;\'
en1 Английский rembocoder 2020-10-29 02:45:59 524 Initial revision for English translation
ru2 Русский rembocoder 2020-10-29 02:44:57 8
ru1 Русский rembocoder 2020-10-29 02:44:38 500 Первая редакция (опубликовано)