Minimum Swaps 2-对向量进行升序排序所需的最小交换数量

Question

我正在做一个相当简单的HackerRank测试，它要求用户编写一个函数，该函数返回按升序排序无序向量所需的最小交换次数，例如

开始: 1，2，5，4，3

结束: 1，2，3，4，5

最小互换次数:1

我已经写了一个函数，它可以处理13/14个测试用例，但是对于最后一个用例来说太慢了。

#include<iostream>
#include<vector>

using namespace std;


int mimumumSwaps(vector<int> arr) {
    int p = 0;  // Represents the (index + 1) of arr, e.g. 1, 2, ..., arr.size() + 1 
    int swaps = 0;

    for (vector<int>::iterator i = arr.begin(); i != arr.end(); ++i) {
        p++;
        if (*i == p)    // Element is in the correct place
            continue;
        else{   // Iterate through the rest of arr until the correct element is found
            for (vector<int>::iterator j = arr.begin() + p - 1; j != arr.end(); ++j) {
                if (*j == p) {  
                    // Swap the elements
                    double temp = *j;
                    *j = *i;
                    *i = temp;

                    swaps++;
                    break;
                }
            }
        }
    }
    return swaps;
}


int main()
{
    vector<int> arr = { 1, 2, 5, 4, 3 };

    cout << mimumumSwaps(arr);

}

我该如何进一步加速呢？

有没有我可以导入的函数，可以为我加快处理速度？

有没有一种方法可以做到这一点，而不需要实际交换任何元素并简单地计算出min。我认为可以加快处理时间的交换？

Answer 1

所有的排列都可以分解成循环子集。找到所述子集。

将K个元素的子集旋转1需要K-1个交换。

遍历数组，直到发现一个元素不在位置为止。走这个循环，直到它完成。前进，跳过已经放入循环中的元素。每个周期的Sum (大小为-1)。

若要跳过，请维护一组有序或无序的未检查项目，并在检查时快速删除它们。

我认为这给出了O(n lg n)左右的最优交换计数。

Answer 2

#include <bits/stdc++.h>
#include <vector>
#include <algorithm>

using namespace std;

int minimumSwaps(vector<int> arr)
{
    int i,c,j,k,l;
    
    j=c=0;
    l=k=arr.size();
       
        while (j<k)
        {
            i=0;
                while (i<l)
                {
                     if (arr[i]!=i+1)
                     {
                         swap(arr[i],arr[arr[i]-1]);
                         c++;
                     }    

                  i++;

                }

         k=k/2;
         j++;

        }

return c;

}

int main()
{
    int n,q;
    cin >> n;
    
    vector<int> arr;
    
    for (int i = 0; i < n; i++)
    {
        cin>>q;
        arr.push_back(q);
    }
    
    int res = minimumSwaps(arr);
    cout << res << "\n";

return 0;
}