Efficiently normalize an array in C++

Question

I am looking for a way to normalize an array efficiently in C++, Normalization means converting all of your array values into values lower than or equal to n. So this:

5235 223 1000 40 40

Becomes:

4 2 3 1 1 or 3 1 2 0 0

Here are my codes

vector<int> normalize_array(vector<int> arr){
    vector<int> tmp(arr), ret(arr.size());

    sort(tmp.begin(), tmp.end());

    for (int i = 0; i < arr.size(); ++i){
        vector<int>::iterator iter = find(tmp.begin(), tmp.end(), arr[i]);
        ret[i] = std::distance(tmp.begin(), iter);
    }

    return ret;
}

The output is 4 2 3 0 0, the above codes can not handle duplicate elements very well. Is there any better way to do that?

Answer 1

Applying tweaks as stated in comments, and using C++ lambdas:

vector<int> normalize_array(const vector<int> &arr /* O(1) */) {
    vector<int> tmp(arr) /* O(N) */, ret(arr.size()) /* O(1) */;

    sort(tmp.begin(), tmp.end()); // O(N lg N)

    transform(arr.cbegin(), arr.cend(), ret.begin(), [&tmp](int x) {
        return distance(tmp.begin(), lower_bound(tmp.begin(), tmp.end(), x));
    }); // O(N lg N)

    return ret; // O(1) by move semantics
} // O(1) + O(N) + O(1) + O(N lg N) + O(N lg N) == O(N lg N)

Live Example

In the following solution, inspired upon @sachse's answer but using C++11, fixes your problem with correct normalization, to produce 4 2 3 1 1, as I believe is what is expected:

vector<int> normalize_array(const vector<int> &arr) {
    if (arr.empty())
        return {};

    vector<int> idx(arr.size()), ret(arr.size());

    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(),
         [&arr](int i, int j) { return arr[i] < arr[j]; });

    ret[idx[0]] = 1;
    for (size_t i = 1; i < arr.size(); ++i) {
        ret[idx[i]] = ret[idx[i - 1]] + (arr[idx[i]] != arr[idx[i - 1]]);
    }

    return ret;
}

Live Example

Answer 2

If you define normalization that way (mathematicians would probably say that normalization is something quite different) it becomes a problem of sorting (you are efficiently creating an array of indexes of ascending values). So I guess you should look at sorting algorithms and use them for your case.

You just need to take into account that elements with the same value have the same index - which usually sorting algorithms do not do.