从提供的数字列表中查找最大连接数。需要帮助调试

Question

问题陈述：

输入格式：输入的第一行包含一个整数n。第二行输入包含 n 个数组元素

输出格式：所有数组元素可以组成的最大数

限制：1<=n<=100 and 1<=array elements<=1000

简单的排序算法不适用于以下输入：2,21 输出为 212，但最大数字为 221

因此我想出了以下算法：

1. 按照 MSD（最高有效数字）对所有数字进行降序排序
2. 找出具有相同msd的元素范围
3. 在包含相同 msd 元素的每个范围内，我们根据升级函数返回的值对每个元素进行排序。升级功能不会改变元素的值。

---

升级函数根据以下基础返回一个值：

如果元素等于 1000，则返回 -1，这导致它被放置在数组的末尾

如果元素是单个数字并且等于其范围的 msd，我们返回 msd100 + msd10 + msd

如果元素是两位数并且等于 msd10 + msd，我们返回 msd100 + msd*10 + msd

如果元素是两位数，我们返回元素*10

在其他情况下我们返回元素

---

我想出了这个算法，考虑了输入 532, 5 , 55 ,56 最大数量应为 56,555,532

我的代码：

#include<stdio.h>
#include<stdlib.h>
void sort_msd(int arr[],int n);
void range_provider_msd(int arr[], int n); // finds out the indexes within which elements of same msd are present
void swap(int a,int b, int arr[]); // swaps array elements with index a and b in array arr[]
int msd(int n); //finds msd of n
void sort_final(int range_left,int range_right,int arr[], int msd_); //gives the final sort on the basis of upgrade function
int upgrade(int n,int msd_);    //upgrades element for better comparison
int main()
{

    int n; //n is number of element in array
    scanf("%d",&n);
    int*arr=(int*)malloc(n*sizeof(int));
    for(int i=0;i<n;++i){scanf("%d",&arr[i]);}

    sort_msd(arr,n); //soritng according to msd

    range_provider_msd(arr,n); 
    for(int i=0;i<n;++i){printf("%d",arr[i]);}

return 0;
}
void sort_msd(int arr[],int n)
{
    for(int i=0;i<n;++i)
    {
        int max_index=i,max_msd=msd(arr[i]);
        for(int j=i+1;j<n;j++)
        {
            int compare_msd=msd(arr[j]);
            if(compare_msd>max_msd)
            {
                max_index=j;
                max_msd=compare_msd;
            }
        }
        swap(i,max_index,arr);
    }
}
int msd(int n)
{
    while(n>=10)
    {
        n=n/10;
    }
    return n;
}
void swap(int a,int b, int arr[])
{
    int temp=arr[a];
    arr[a]=arr[b];
    arr[b]=temp;
}
void range_provider_msd(int arr[], int n)
{
    //following code finds out the index ranges for elements with same msd and passes them onto the sort_final function
    int left_range=0,right_range=0;
    for(int i=1;i<(n+1);++i) //n+1 to check for the special case for last elements being equal
    {
        if(msd(arr[left_range])-msd(arr[i]) == 0 && left_range<n-1 && i<n)
            ++right_range;
        else if(right_range== n-1 && i==n) //special code when last elements are equal
        {
            sort_final(left_range,right_range,arr,msd(arr[left_range]));
        }
        else 
        {
            sort_final(left_range,right_range,arr,msd(arr[left_range]));            
            left_range=right_range+1;
            ++right_range;
        }
    }
}

void sort_final(int range_left,int range_right,int arr[],int msd_)
{
    for(int i=range_left;i<=range_right;++i)
    {
        int max_index=i;
        for(int j=i+1; j<=range_right;++j)
        {
           if(upgrade(arr[j],msd_)>upgrade(arr[max_index],msd_))
           max_index=j; 
        }
        swap(i,max_index,arr);
    }
}

int upgrade(int n, int msd_)
{
    if(n==1000)
        return -1;
    else if(n<10 && n==msd_)
        return(100*msd_ + 10*msd_ + msd_);
    else if(n>=10 && n<100 && n==(10*msd_+msd_))
        return(100*msd_ + 10*msd_ + msd_);
    else if(n>=10 && n<100)
        return(n*10);
    else
        return(n); 
}

我在评分系统上提交了此代码，并在 11 次测试中的第 9 次测试中陷入困境，并且测试没有指定我陷入困境的输入。 有人可以帮我找到程序无法输出正确答案的情况吗？ 或者有没有更简单、明显的方法来解决这个问题？ 我对数据结构或类似的东西一无所知。任何帮助将不胜感激。谢谢你

p.s 这是我在加州大学圣地亚哥分校的 coursera 课程“算法工具箱”中的作业之一。

Answer 1

任何人都可以帮我找到程序无法输出正确答案的情况吗？

尝试

int n = 2;
int*arr=(int*)malloc(n*sizeof(int));
arr[0] = 56;
arr[1] = 561;

您的代码将给出

56156

但你本可以形成

56561