首页 > 代码库 > 题目1504：把数组排成最小的数

题目1504：把数组排成最小的数

2024-07-27 03:39:55   221人阅读

题目描述：
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
输入：
输入可能包含多个测试样例。
对于每个测试案例，输入的第一行为一个整数m (1<=m <=100)代表输入的正整数的个数。
输入的第二行包括m个正整数，其中每个正整数不超过10000000。
输出：
对应每个测试案例，
输出m个数字能排成的最小数字。
样例输入：
3
23 13 6
2
23456 56
样例输出：
13236

2345656

//方法一

#include <iostream>
#include<string>
#include<vector>
#include<cstdlib>
#include<algorithm>
using namespace std;
/*
 *字符串比较，长度相同直接比较
 *长度不同时，先比较长度相同的部分，若长度相同的部分不相同，则直接进行比较即可;
 *长度相同的部分相同的，再将长字符串的剩下的部分与短字符串比较;
 *另外，排序函数的使用需要注意到地方还有很多，qsort(str,0,str+n,cmp);很漂亮的用法。而用容器则直接用begin(),end()函数替代
 *cmp比较函数的设计，注意返回值为int类型
 *字符串的比较，用标准模板库里面的函数真的是相当方便，各种函数用的好了很方便，用的不好，错误一堆
 */
bool cmp(string str1,string str2)
{
    int flag;
    bool isBig;
    int len1=str1.length(),len2=str2.length();
    if(len1==len2)
        flag=str1.compare(str2);
    else
    {
        if(len1<len2)
        {
            if(str2.compare(0,len1,str1)==0)
            {
               isBig=cmp(str1,str2.substr(len1,len2-len1));
               if(isBig)
                return true;
               else
                return false;
            }
 
            else
                flag= str1.compare(str2);
        }
        else
        {
            if(str1.compare(0,len2,str2)==0)
            {
                isBig=cmp(str1.substr(len2,len1-len2),str2);
                if(isBig)
                    return true;
                else
                    return false;
            }
            else
                flag= str1.compare(str2);
        }
    }
    if(flag==1)
        return false;
    else
        return true;
}
/*
 *总体思路：为了便于比较输入的数中的各位数字的大小，首先将输入的数字当成字符串输入；
 *输入结束后，将字符串按题目要求的规则进行排序，详细排序规则详见比较函数；
 *最后，将排序好的字符串直接输出就是所要求的数字，然后输出；
 *bingo！
 */
int main()
{
    int n;
    while(cin>>n)
    {
        string str;
        vector<string>vec;
        for(int i=0;i<n;i++)
        {
            cin>>str;
            vec.push_back(str);
        }
 
        sort(vec.begin(),vec.end(),cmp);
        vector<string>::iterator iter=vec.begin();
        for(;iter!=vec.end();iter++)
        {
            cout<<*iter;
        }
        cout<<endl;
    }
    return 0;
}
 
/**************************************************************
    Problem: 1504
    User: hndxztf
    Language: C++
    Result: Accepted
    Time:170 ms
    Memory:1528 kb
****************************************************************/

//方法二

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
/*
 *首先将字符串进行拼接，再直接比较字符串
 *拼接后避免出现321>32>3的情况，那样就成了332321了
 */
bool cmp(string str1,string str2)
{
 
    string temp1=str1,temp2=str2;
    temp1.append(str2);
    temp2.append(str1);
    return temp1<temp2;
}
/*
 *总体思路：为了便于比较输入的数中的各位数字的大小，首先将输入的数字当成字符串输入；
 *输入结束后，将字符串按题目要求的规则进行排序，详细排序规则详见比较函数；
 *最后，将排序好的字符串直接输出就是所要求的数字，然后输出；
 *bingo！
 */
int main()
{
    int n;
    while(cin>>n)
    {
        string str;
        vector<string>vec;
        for(int i=0;i<n;i++)
        {
            cin>>str;
            vec.push_back(str);
        }
 
        sort(vec.begin(),vec.end(),cmp);
        vector<string>::iterator iter=vec.begin();
        for(;iter!=vec.end();iter++)
        {
            cout<<*iter;
        }
        cout<<endl;
    }
    return 0;
}
 
/**************************************************************
    Problem: 1504
    User: hndxztf
    Language: C++
    Result: Accepted
    Time:250 ms
    Memory:1528 kb
****************************************************************/

题目1504：把数组排成最小的数


联系
我们