Учитывая массив arr = {5, 16, 4, 7}, мы можем сортировать его через sort(arr, arr+sizeof(arr)/sizeof(arr[0])).
поэтому теперь массив arr = {4, 5, 7, 16} и индекс перестановки для отсортированного массива {2, 0, 3, 1}.
Другими словами, arr[2] в исходном массиве теперь является самым маленьким элементом в отсортированном массиве в позиции 0.
Есть ли эффективный способ, чтобы мы могли получить индекс перестановки?
Спасибо
Создайте массив индексов, заполните его цифрами 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;
}
Почему бы не поместить некоторые спутниковые данные? Вместо сортировки чисел просто сортируйте пары чисел и их индексы. Поскольку сортировка сначала выполняется на первом элементе пары, это не должно нарушать стабильный алгоритм сортировки.
Для нестабильных алгоритмов это изменит его на стабильный.
Но обратите внимание, что если вы попытаетесь сортировать этот путь, он генерирует индекс при сортировке, а не после.
Кроме того, поскольку знание индекса перестановки приведет к алгоритму сортировки O (n), вы не сможете сделать это быстрее, чем O (nlogn).
Хорошо в С++ мы можем использовать пару типов данных, чтобы сделать это легко. Пример кода ниже;
arr = {5, 16, 4, 7};
vector<pair<int,int> >V;
for(int i=0;i<4;i++){
pair<int,int>P=make_pair(arr[i],i);
V.push_back(P);
}
sort(V.begin(),V.end());
Итак, V [i]. Первое - это i-е значение, а V [i]. второй - i-й индекс. Поэтому для печати индекса в отсортированном массиве.
for(int i=0;i<4;i++)cout<<V[i].second<<endl;
Обратите внимание, что при сортировке массива (или вектора) парных элементов массив сначала сортируется на основе первых значений. Если две пары имеют одно и то же первое значение, то они сортируются на основе их второго значения.
Multimap может прийти на помощь
template<typename TIn, typename TOut>
sortindex(const TIn &first, const TIn &last, TOut &out) {
using ValT = typename std::decay<decltype(*first)>::type;
std::multimap<ValT, size_t> sindex;
for(auto p=first; p != last; p++)
sindex.emplace(*p, std::distance(first, p));
for(auto &&p: sindex)
*out++ = p.second;
}
который можно использовать следующим образом:
std::vector<size_t> a{32, 22, 45, 9, 12, 15};
std::vector<size_t> indexes;
sortindex(a.begin(), a.end(), std::back_inserter(indexes));
Если связь между отсортированными значениями и индексом будет необходима, тогда многомазна может быть непосредственно возвращена, а не записывать индексы в выходной итератор.
template<typename TIn>
auto
sortindex(const TIn &first, const TIn &last)
--> std::multimap<typename std::decay<decltype(*first)>::type, size_t>
{ // return value can be commented out in C++14
using ValT = typename std::decay<decltype(*first)>::type;
std::multimap<ValT, size_t> sindex;
for(auto p=first; p != last; p++)
sindex.emplace(*p, std::distance(first, p));
return sindex;
}
Недавно мне пришлось решить аналогичную проблему в PHP. Вы создаете локальную функцию сравнения, которая будет использоваться алгоритмом сортировки PHP UASORT. Вызовите array_keys() в отсортированном массиве, и это должно выплюнуть ваш массив перестановок.
//тестовый массив
$tArray = array ('2', '10', '1', '23', '8', '3');
//сортировать массив; поддерживать ассоциацию индексов, использовать uasort; иначе используйте usort и т.д.
uasort ($ tArray, 'compareSize');
//Полученные ключи - это ваши индексы перестановок (если используется uasort на предыдущем шаге)
$Keys = array_keys ($ tArray);
//функция локального сравнения
function compareSize ($ a, $b) {
if ($ a == $b) {return 0; } else {return ($ a < $b)? -1:1; }
}
=============================================== ======================== Результаты:
sorted =: Array ([2] = > 1 [0] = > 2 [5] = > 3 [4] = > 8 [1] = > 10 [3] = > 23)
keys =: Array ([0] = > 2 [1] = > 0 [2] = > 5 [3] = > 4 [4] = > 1 [5] = > 3)
Я думаю, мы сможем решить эту проблему без использования вектора. Я новичок, честно говоря, я не понимаю, что вы написали выше, и все вы использовали вектор, который я буду изучать позже:))) (я ленив) Здесь мой путь:
//Сначала скопируем массив a [] в массив b []
void copyarray(double b[],double a[],int n){
for(int i=0;i<n;i++)b[i]=a[i];
}
//Во-вторых, сортируем массив a [] (уменьшение)
/* В-третьих, массив "сортировщик" a [], это означает: в массиве a [], если существуют одинаковые значения, они будут сливаться в один! я будет устанавливать массив o [] - это отсортированный массив a [] "*/
void sorter(double o[],double a[],int n,int &dem){
int i;
o[0]=a[0];
for(i=1;i<n;i++){
if(a[i]!=a[i-1]){
dem++; o[dem]=a[i];
}
}
dem++;
}
/* 4, наша главная цель: получить индекс: я поместит индекс в массив c [] */
void index_sort(double o[],double b[], double c[], int dem, int n){
int i,j,chiso=0;
for(j=0;j<dem;j++){
for(i=0;i<n;i++){
if(b[i]==o[j]){
c[chiso]=i;
chiso++;
}
}
}
}
// DONE!
int main(){
int n,dem=0;
double a[100],b[100],c[100],o[100];
cin>>n;
input(a,n);
copyarray(b,a,n);
copyarray(c,a,n);
sort(a,n);
sorter(o,a,n,dem);
index_sort(o,b,c,dem,n);
for(int i=0;i<n;i++) cout<<c[i]<<" ";
}
Да, есть один с O(NlogN) time.S так как сортировка занимает O(NlogN) время в любом случае, это не повлияет на общую сложность времени.
Сложность времени: O(NlogN)
Космическая сложность: O(N)
где N= количество элементов в массиве ввода
Алгоритм: