排序后如何获取索引排列

小编典典

排序后如何获取索引排列

algorithm

给定一个数组arr = {5, 16, 4, 7}，我们可以对其进行排序sort(arr, arr+sizeof(arr)/sizeof(arr[0]))。所以现在数组arr = {4, 5, 7, 16}和排序后的数组的排列索引是{2, 0, 3, 1}。换句话说，arr[2]原始数组中的in现在是position中排序数组中最小的元素0。

是否有一种有效的方法来获取置换索引？

谢谢

阅读 387

2020-07-28

共1个答案

小编典典

创建一个索引数组，将其填充为数字0..N-1，然后使用自定义比较器对其进行排序。比较器应比较原始数组中索引lhs和的项目rhs。以这种方式对索引数组进行排序将它们重新排列为排列：

vector<int> data = {5, 16, 4, 7};   
vector<int> index(data.size(), 0);
for (int i = 0 ; i != index.size() ; i++) {
    index[i] = i;
}
sort(index.begin(), index.end(),
    [&](const int& a, const int& b) {
        return (data[a] < data[b]);
    }
);
for (int i = 0 ; i != index.size() ; i++) {
    cout << index[i] << endl;
}

此打印 2, 0, 3, 1

这是有关ideone的演示。

注意：您可以使用index检索已data排序的顺序：

for (int i = 0 ; i != index.size() ; i++) {
    cout << data[index[i]] << endl;
}

2020-07-28