给一个数列问将其排序递增或者递减序列的最小交换次数.
一. 只能交换相邻元素
该情况下最少交换次数即为逆序数的数目, 求逆序数只要从 1~n 遍历数组, 每次添加一个数字到树状数组然后求前缀和即可
二. 可以交换任意位置的元素
例如 2 4 3 1, 可以知道 1 应该与 2 交换, 而 2 应该与 4 交换, 4 应该与 1 交换, 这样就形成一个循环 (3 应该与本身交换可以看作自环), 易知这样的循环中如果有 x 个数, 只要交换 x-1 次就能将这个循环内的大小顺序排好, 而不同的循环之间是不会影响的, 所以假如 n 个数有 k 个循环, 每个循环有 ai 个数, 则交换次数应该为 (a1-1)+ (a2-1) + ... + (ak-1) = n-k, 即数组数目减循环个数, 求循环个数直接对数组建图然后 dfs 一遍即可
来源: http://www.bubuko.com/infodetail-2788189.html