交换最少次数使数组有序

交换最少次数使数组有序

题目1：
给出一个序列，只交换相邻两数，使得序列升序排列，求出最少交换次数。

思路：
如果说只是交换相邻两个数字。那么就是这个序列的逆序数。

1.假设序列个数为n，我们先把最大的数换到最后，因为是相邻数字交换，所以把最大数交换到最后，需要交换的次数为最大数后的数字个数。

2.当完成最大数的交换后，可以将最大数从序列中划去不管了，即此时序列个数为n-1了，我们再在该序列中找到一个最大数，进行相同操作。

3.所以使整个序列有序的交换次数为,这个序列的所有逆序总数。

比如4，3，2，1。
(4,3) (4,2) (4,1)，有3个逆序，交换后 3，2，1，4
(3,2) (3,1)，有2个逆序，交换后2,1,3,4
(2,1)，有1个逆序，交换后1,2,3,4

用归并的方法写了一个。

class Solution {
public:// 维护一个 有序序列int reversePairs(vector<int>& nums) {int len = nums.size();if(len < 2) return 0;vector<int> copy(nums.begin(), d() );vector<int> temp(len, 0);// 首先 拷贝一份 nums, 放在 copy中，传入计算中return mergeAndCnt(copy, 0, len -1, temp);}// 计算逆序对个数 并且排序int mergeAndCnt(vector<int>& nums, int left, int right, vector<int>& temp){if(left == right) return 0;int mid = left + (right - left) / 2; // 中间或靠前的一个元素int leftPairs = mergeAndCnt(nums, left, mid, temp);int rightPairs = mergeAndCnt(nums, mid + 1, right, temp);if(nums[mid] <= nums[mid + 1]) return leftPairs + rightPairs;int crossPairs = mergeAndCount(nums, left, mid, right, temp); // 为什么 nums 和 temp 总是同时出现呢return leftPairs + rightPairs + crossPairs;}// 折int mergeAndCount(vector<int>& nums, int left, int mid, int right, vector<int>& temp){// temp 用以备份 nums 中的数值// temp 只保存 index [left, right]for(int i = left; i <= right; i++) temp[i] = nums[i];int i = left;int j = mid + 1;int count =0;for(int k = left; k <= right; k++){// 有下标越界， 先判断是否越界, 归并排序还能这么写if(i == mid + 1){nums[k] = temp[j];j++;} else if(j == right + 1){nums[k] = temp[i];i++;} else if(temp[i] <= temp[j]){nums[k] = temp[i];i++;} else{nums[k] = temp[j];j++;count += (mid - i + 1);}}return count;}};

题目2：
给出一个序列，可交换任意两个数，使序列升序排列，求最少交换次数。

思路：
与之前不同，之前是只能交换相邻两数。
比如4，3，2，1，如果只交换相邻两数，最少交换次数为6。
但如果是交换任意两数，最少交换次数就为2。

有序列5，4，3，2，1。共5个数。

nums [0] [1] [2] [3] [4]
5 4 3 2 1
1
2
按升序排列之后为

nums1 [0] [1] [2] [3] [4]
1 2 3 4 5
1
2
我们可以发现5，1虽然不在自己应该在的位置，但是如果把它们两个看成整体，对于整个序列来说它们占据了排好序后5，1应该在的位置，所以对于整个序列来说是有序的，它们只是自身内部无序而已。5应该到1处，1应该到5处，形成了一个循环，所以可以将它们抽象成一个环，环内换序就可以了。(下面把这种环称为循环节)
对于一个含有n个元素的循环节来说，要使其有序，要交换n-1次(前面都排好了，最后一个数自然有序就不用排了)。
上例中3在原本就在的位置，可以看成一个元素的循环节。
我们可以推断出有一个循环节，就可以少交换一次，因为n个元素的循环节，只需交换n-1次即可有序。
那么对于整个序列来说，最少交换次数为 元素总数-循环节个数。

5，4，3，2，1序列中有3个循环节，所以最少交换次数为2。

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
int getMinSwaps(vector<int> &nums){//排序vector<int> nums1(nums);sort(nums1.begin(),d());unordered_map<int,int> m;int len = nums.size();for (int i = 0; i < len; i++){m[nums1[i]] = i;//建立每个元素与其应放位置的映射关系}int loops = 0;//循环节个数vector<bool> flag(len,false);//找出循环节的个数for (int i = 0; i < len; i++){if (!flag[i]){//已经访问过的位置不再访问int j = i;while (!flag[j]){flag[j] = true;j = m[nums[j]];//原序列中j位置的元素在有序序列中的位置}loops++;}}return len - loops;
}
int main()
{vector<int> nums;//3, 7, 1, 6, 2, 4, 8, 5nums.push_back(3);nums.push_back(7);nums.push_back(1);nums.push_back(6);nums.push_back(2);nums.push_back(4);nums.push_back(8);nums.push_back(5);int res=getMinSwaps(nums);system("pause");return 0;
}

参考：