c++ - 如何订购具有重复值的数组？

Question

我想订购一系列可能有重复的东西。例如:

int values[5] = {4, 5, 2, 5, -1};
int expected[5] = {1, 2, 0, 2, -1};

这里 2 是最小的元素，所以它的阶数是 0。4 是第二小的，所以它的阶数是 1。5 是第三小的，我希望它们的阶数都是 2。我想跳过某些元素 ( -1 在上面的例子中)所以这些元素的顺序是 -1。

我如何在 C++ 中执行此操作或描述算法？

谢谢

Answer 1

只需对数组进行排序，然后为每个元素分配其等级:

vector<int> v(values, values + 5);
v.push_back(-1);
sort(begin(v), end(v));
v.resize(unique(begin(v), end(v)) - begin(v));
for (int i = 0; i < 5; ++i)
  expected[i] = lower_bound(begin(v), end(v), values[i]) - begin(v) - 1;

这假设所有元素都是非负数或 -1。如果存在小于-1 的负数元素，则需要对-1 进行特殊处理。