使序列有序的最少交换次数

106 阅读 0 评论 70 点赞

我是靠谱客的博主大气睫毛膏，最近开发中收集的这篇文章主要介绍使序列有序的最少交换次数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目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

用归并的方法写了个。

代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
int cnt;
int arr[1005];
void Merge(int* arr,int* tmp,int left,int right,int rightEnd){
int leftEnd = right - 1;
int start = left;
while (left <= leftEnd && right <= rightEnd){
if (arr[left] > arr[right]){
tmp[start++] = arr[right++];
cnt += (leftEnd - left+1); //如果当前left位置上的数大于right位置上的数，那么从left到leftEnd所有的数都大于
}
else{
tmp[start++] = arr[left++];
}
}
while (left <= leftEnd){
tmp[start++] = arr[left++];
}
while (right <= rightEnd){
tmp[start++] = arr[right++];
}
}
void MergeSort(int* arr,int* tmp,int n,int length)//length当前有序子列的长度
{
int i;
for (i = 0; i <= n - 2 * length; i += 2 * length){
Merge(arr,tmp,i,i+length,i+2*length-1);
}
//最后剩下两个子列，进行归并
if (i + length < n){
Merge(arr,tmp,i,i+length,n-1);
}
else{//只剩最后一个子列，不能成对
for (int j = i; j < n; j++){
tmp[j] = arr[j];
}
}
}
void Merge_Sort(int* arr,int n){
int lenght = 1;
int* tmp = (int *)malloc(sizeof(int)*n);
while (lenght < n){
MergeSort(arr,tmp,n,lenght);
lenght *= 2;
MergeSort(tmp,arr,n,lenght);
lenght *= 2;
}
free(tmp);
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
memset(arr,0,sizeof(arr));
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
cnt=0;
Merge_Sort(arr,n);
printf("%dn",cnt);
}
return 0;
}

题目2：

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

思路：

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

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

nums [0] [1] [2] [3] [4]
5
4
3
2
1

按升序排列之后为

nums1 [0] [1] [2] [3] [4]
1
2
3
4
5

我们可以发现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(),nums1.end());
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, 5
nums.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;
}