欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构PTA 案例7-1.5 与零交换

程序员文章站 2024-01-11 14:24:16
案例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...

案例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

解法

思路
这道题目抽象出来,是一道表排序的题,就是寻找“环”。
数据结构PTA 案例7-1.5 与零交换
上图中有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