У меня есть вопрос по поводу минимального свопа на Hackerrank.
По сути, вопрос заключается в том, чтобы найти количество перестановок, необходимое для сортировки массива.
Массив не содержит дубликатов элементов.
Вот мой код, но, похоже, я получил неправильный ответ. В частности, я получаю 4-кратную длину массива для вектора temp.
int minimumSwaps(vector<int> arr) {
int n = arr.size();
int count_swap = 0;
vector<int> temp;
for(int i = 0; i < n; ++i){
cout << temp.size()<<"\n";
if(arr[i] == i+1){
temp.push_back(arr[i]);
}
else{
int initial_val = arr[i];
int next_val = arr[arr[i] - 1];
temp.push_back(initial_val);
while(next_val != initial_val){
temp.push_back(next_val);
next_val = arr[next_val - 1];
count_swap += 1;
}
}
if (temp.size() == n){
break;
}
}
print(temp);
return count_swap;
}
Мой подход состоял в том, чтобы найти циклический цикл в массиве, и минимальное количество замен должно быть этим числом - 1.
Так, например, если у нас есть arr = [2,3,4,1,5]
2 -> 3 -> 4 -> 1 -> 2
Так чтоэто цикл длины 4. Следовательно, минимальный своп 4-1 = 3. (Поскольку остальные 5 уже на месте и будут иметь длину цикла = 1, следовательно, требуется 0 замен).