You are viewing a single comment's thread. Return to all comments →
One may want to remap the values into, say, 0, 1, ..., n - 1 ordered in the same way. This is possible in O(n log n) time:
vector<int> GetMap(const vector<int>& arg){ vector< pair<int, int> > valToIndex; for (int i = 0; i < arg.size(); ++i){ valToIndex.emplace_back(make_pair(arg[i], i)); } sort(valToIndex.begin(), valToIndex.end()); vector<int> res(arg.size()); for (int i = 0; i < arg.size(); ++i){ res[valToIndex[i].second] = i; } return res; }
As a side note, I really hope that there will be no new testcases with repeated entries. The problem with repeated entries is likely to be NP-hard for reasons similar to https://math.stackexchange.com/questions/2419271/decomposition-of-edges-of-eulerian-graph-into-maximum-number-of-cycles
Seems like cookies are disabled on this browser, please enable them to open this website
Minimum Swaps 2
You are viewing a single comment's thread. Return to all comments →
One may want to remap the values into, say, 0, 1, ..., n - 1 ordered in the same way. This is possible in O(n log n) time:
As a side note, I really hope that there will be no new testcases with repeated entries. The problem with repeated entries is likely to be NP-hard for reasons similar to https://math.stackexchange.com/questions/2419271/decomposition-of-edges-of-eulerian-graph-into-maximum-number-of-cycles