无序数组交换任意两个元素最少交换次数

题目：

属于是经典题了，做完可以去做一下 UOJ233 【IOI2015】Sorting （确信

给定长度为 $n$ 的排列，将元素升序排序，每次可以交换任意两个元素，最少要交换几次？

如果是交换相邻两个元素，那就是逆序对的个数，这个本文不会提及（~~因为已经说完了~~

例：

input:
6
1 4 2 3 5 6

output: 
2
swap 2 4
swap 4 3

题解：

对于每个元素，我们将该元素和它的正确位置建边

最后一定是 $1\sim n$ 个环（自环也算）

对于有 $k$ 个元素的环，最少交换次数为 $k-1$

假设共有 $p$ 个环，对于第 $i$ 个环，有 $k_i$ 个元素，则它的最少交换次数为 $k_i - 1$

因此

$\mathtt{ans} = \sum\limits_{i=1}^{p}{(k_i-1)} = \sum\limits_{i=1}^{p}{k_i} - p$

显然

$n = \sum\limits_{i=1}^{p}{k_i}$

所以答案就是 $n-p$ ，即元素个数 - 环的个数。具体实现见代码。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6+15))

int n,a[N],p[N],q[N],tag[N];
void work()
{
    int cur=0;
    for(int i=1; i<=n; i++)
        if(tag[i] != 1)
        {
            for(int j=i; tag[j] != 1; j=a[j])
                { tag[j]=1; p[cur]=j; q[cur++]=a[j]; }
            --cur;
        }
    
    cout << cur << '\n';
    for(int i=0; i<cur; i++)
        cout << "swap " << p[i] << ' ' << q[i] << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; for(int i=1; i<=n; i++) cin >> a[i]; work();
    return 0;
}

其他解法：

不知道啥时候写的垃圾东西，看个乐呵或者不看都没关系了啦！

我们可以遍历一遍原数组，如果当前元素不在正确位置上，将该元素和此时在它正确位置上的元素交换

这里有一个要注意的，某次交换后我们可能没有将交换和被交换数都放在正确位置上，且有可能在接下来的遍历中不会再次遍历到被交换数，因此交换后还要再判断，直到当前位置的数正确，显然不这么做不会影响正确结果

很容易证明这是最少的。

设当前元素为 $\alpha$ （不在正确位置上），它与非 $\alpha$ 的正确位置上的元素 $\beta$ 交换，会有两种情况：第一种， $\beta$ 在正确位置上。由于最后 $\beta$ 一定会在正确位置上，且一定是 $\beta$ 和在 $\beta$ 正确位置上的元素交换（或 $\beta$ 本来就在正确位置），所以交换 $\alpha$ 和 $\beta$ 就是多余的；第二种， $\beta$ 不在正确位置上。显然对于每次必要交换，我们不在乎正确位置上的元素是什么，我们只需要将正确的元素与其交换就可以了，至于被交换的元素，我们会接下来处理它，所以交换 $\alpha$ 和 $\beta$ 是多余的

由于我们要知道正确位置，所以要排序好的数组记录正确位置，时间复杂度 $\mathcal{O}(n\log n)$

主要代码如下：

int fun(vector<int> a)
{
    vector<int>tmp=a;//排序后的数组
    map<int,int>mp;
    int ans=0;
    sort(tmp.begin(),tmp.end());
    for(int i=0; i<tmp.size(); i++)
        mp[tmp[i]]=i;//记录每个对应的正确位置
    for(int i=0; i<a.size(); i++)
        while(i!=mp[a[i]])
        {
            ans++;
            swap(a[i],a[mp[a[i]]]);
        }
    return ans;
}