将 { 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]是自环路,不需要做位置上的调整,所以在计算环的数量的时候,不考虑这种自环路。
对于以上的计算公式,可以自己列举例子推算得到
实现
#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
如对本文有疑问, 点击进行留言回复!!
微信小程序 show-menu-by-longpress base64图片 ios下载图片无效
20200810 airtest查看当前设备安装app 截图
ASP.NET Core Authentication认证实现方法
网友评论