数据结构PTA 案例7-1.5 与零交换
程序员文章站
2022-03-20 12:53:21
案例7-1.5 与零交换题目解法题目将 { 0, 1, 2, …, N-1 } 的任意一个排列进行排序并不困难,这里加一点难度,要求你只能通过一系列的 Swap(0, *) —— 即将一个数字与 0 交换 —— 的操作,将初始序列增序排列。例如对于初始序列 { 4, 0, 2, 1, 3 },我们可以通过下列操作完成排序:Swap(0, 1) ⟹ { 4, 1, 2, 0, 3 }Swap(0, 3) ⟹ { 4, 1, 2, 3, 0 }Swap(0, 4) ⟹ { 0, 1, 2, 3, 4...
题目
将 { 0, 1, 2, …, N-1 } 的任意一个排列进行排序并不困难,这里加一点难度,要求你只能通过一系列的 Swap(0, *) —— 即将一个数字与 0 交换 —— 的操作,将初始序列增序排列。例如对于初始序列 { 4, 0, 2, 1, 3 },我们可以通过下列操作完成排序:
Swap(0, 1) ⟹ { 4, 1, 2, 0, 3 }
Swap(0, 3) ⟹ { 4, 1, 2, 3, 0 }
Swap(0, 4) ⟹ { 0, 1, 2, 3, 4 }
本题要求你找出将前 N 个非负整数的给定排列进行增序排序所需要的最少的与 0 交换的次数。
输入格式:
输入在第一行给出正整数 N (≤105 );随后一行给出{ 0, 1, 2, …, N-1 } 的一个排列。数字间以空格分隔。
输出格式:
在一行中输出将给定序列进行增序排序所需要的最少的与 0 交换的次数。
输入样例:
10
3 5 7 2 6 4 9 0 8 1
输出样例:
9
解法
思路
这道题目抽象出来,是一道表排序的题,就是寻找“环”。
上图中有3个环,但是A[2]是自环路,不需要做位置上的调整,所以在计算环的数量的时候,不考虑这种自环路。
- 首先要区别第一个数组元素是否为0,它对交换次数的计算公式有影响,可以用一个flag变量标记。
- 用FindNextIndex函数来寻找,哪个数组元素的下标和它的值不同,接着用顺着这个值去寻找下一个元素,直到环封闭。此时计算环的数量CN变量需要加1。
- 如果用FindNextIndex函数,每次都从头开始检查,那么会大大增加程序的时间复杂度(我第一次就是这么做的),最好的方法是记录从环退出的位置,这个位置之前的元素一定是排好的,寻找下一个环开头,只需要在这个元素之后寻找就行。
- 交换次数计算公式:
- 如果没有环,自然交换次数CT=0;
- 如果最开始,第一个元素为0,那么需要用所有环的元素数量BasicN,加上环的个数
- 如果最开始,第一个元素不为0,那么需要用所有环的元素数量BasicN,加上环的个数-1,再减去1(这个1是专门针对第一个环的)
对于以上的计算公式,可以自己列举例子推算得到
实现
#include<stdio.h>
void InputNumber(int *P, int N)
{
int i;
for(i=0; i<N; i++)
{
scanf("%d", &P[i]);
}
}
int FindNextIndex(int *P, int begin, int N)
{
int i;
for(i=begin; i<N; i++)
{
if(P[i]!=i)
return P[i];
}
return -1;
}
int BasicCount(int *P, int N)
{
int i,count;
count = 0;
for(i=0; i<N; i++)
{
if(P[i]!=i)
count++;
}
return count;
}
int main()
{
int N;
scanf("%d", &N);
int *P = (int *)malloc(N*sizeof(int));
InputNumber(P, N);
// Calculate the number of circles
int CT = 0; //change times
int CN = 0; //circle numbers
int BasicN = BasicCount(P, N);
int flag; //tag the special circle
if(P[0]==0)
flag = 1;
else
flag = 0;
int tmp;
int NextIndex = FindNextIndex(P, 0, N);
int oldNextIndex;
while(NextIndex != -1)
{
while(1)
{
if(P[NextIndex]!=NextIndex)
{
oldNextIndex = NextIndex;
tmp = P[NextIndex];
P[NextIndex] = NextIndex;
NextIndex = tmp;
}
else
break;
}
CN++;
NextIndex = FindNextIndex(P, oldNextIndex, N);
}
if(CN==0)
CT = 0;
if(flag == 0)
CT = BasicN+(CN-1)*1-1;
else
CT = BasicN+CN;
printf("%d", CT);
}
本文地址:https://blog.csdn.net/qq_41773233/article/details/107327022
推荐阅读