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

Question

我正在寻找一种在 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，上面的代码不能很好的处理重复元素。 有没有更好的方法来做到这一点？

Answer 1

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