数据结构PTA 案例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 }
本题要求你找出将前 N 个非负整数的给定排列进行增序排序所需要的最少的与 0 交换的次数。

输入格式：
输入在第一行给出正整数 N (≤10^​5​​ )；随后一行给出{ 0, 1, 2, …, N-1 } 的一个排列。数字间以空格分隔。

输出格式：
在一行中输出将给定序列进行增序排序所需要的最少的与 0 交换的次数。

输入样例：

10
3 5 7 2 6 4 9 0 8 1

输出样例：

9

解法

思路
这道题目抽象出来，是一道表排序的题，就是寻找“环”。

上图中有3个环，但是A[2]是自环路，不需要做位置上的调整，所以在计算环的数量的时候，不考虑这种自环路。

1. 首先要区别第一个数组元素是否为0，它对交换次数的计算公式有影响，可以用一个flag变量标记。
2. 用FindNextIndex函数来寻找，哪个数组元素的下标和它的值不同，接着用顺着这个值去寻找下一个元素，直到环封闭。此时计算环的数量CN变量需要加1。
3. 如果用FindNextIndex函数，每次都从头开始检查，那么会大大增加程序的时间复杂度（我第一次就是这么做的），最好的方法是记录从环退出的位置，这个位置之前的元素一定是排好的，寻找下一个环开头，只需要在这个元素之后寻找就行。
4. 交换次数计算公式：
   • 如果没有环，自然交换次数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