Coordinate Compression aka Normalization

One easy way to normalize an array is to first create a copy of it. Let 'v' be the array to be normalized and 'aux' its duplicate. Then, sort the copy and erase the duplicates. Thus, 'aux' contains all the distinct elements in 'v'. Now, we simply have to find for each element in 'v' its position in 'aux'. This can be easily done using binary search or the STL-provided lower_bound() function.

/// @brief Normalize {v} into range [1 - N]
///        where {N} is the maximum element in {v}
void Normalize(vector<int>& v) {
	vector<int> aux = v;
	sort(all(aux));
	aux.erase(unique(all(aux)), aux.end());
	for (int i = 0; i < (int) v.size(); i++)
		v[i] = lower_bound(all(aux), v[i]) - aux.begin() + 1;
}