c++ - 在 C++ 中有效地规范化数组

我正在寻找一种在 C++ 中有效规范化数组的方法，规范化意味着将所有数组值转换为小于或等于 n 的值。所以这:
5235 223 1000 40 40
变成:
4 2 3 1 1 或 3 1 2 0 0
这是我的代码

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;
}

输出是 4 2 3 0 0 ，上面的代码不能很好地处理重复元素。
有没有更好的方法来做到这一点？

最佳答案

应用评论中所述的调整，并使用 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

在以下解决方案中，受到@sachse 的回答的启发，但使用 C++11，通过正确的规范化解决了您的问题，以生成 4 2 3 1 1 ，正如我认为的那样:

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

关于c++ - 在 C++ 中有效地规范化数组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26729660/