用C++求解最小交换hackerrank问题

Question

我有一个关于Hackerrank最小交换问题的问题。

基本上，问题是找到排序数组所需的交换数。

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;


}

2->3->4->1->2

所以有一个长度为4的循环。因此，所需的最小交换为4-1=3。（因为其他5个已经到位，并且循环长度为1，因此需要0个交换）。

Answer 1

该算法对向量中的每个元素进行迭代，然后继续确定该元素处的循环。因此，它四次遇到第一个周期。该算法可能会对向量中的循环进行迭代。