[已解决]n个整数组合成最大数问题(python表达)

redleafage

题目要求：输入N个整数，自动求出这n个整数能组成的最大数。
比如输入：
3（表示一共有多少个整数）
21 7 82
则直接输出：82721


我的思想是：
1.求出输入的整数的所有可能出现的排列组合，组成一个新列表。
如输入1，2，求出的列表即为：[[1，2],[2，1]]
2.循环新列表中的每个元素，再把每个元素进行循环，组成一个字符串。
即['12','21']
3.求出列表中最大的值
即‘21’

代码如下：

#Users python3
__Author__ = 'Redleafage Zhang'
import sys
import itertools
from operator import itemgetter

def largest_number(a):
    temp= itertools.permutations(a, int(n))
    list = []

    # write your code here
    for i in temp:
        tempstr = ""
        for j in i:
            tempstr += j
        list.append(tempstr)
    res = max(list)

    return res


if __name__ == '__main__':
    input = sys.stdin.read()
    data = input.split()
    n = data[0]
    a = data[1:]
    print(largest_number(a))

整个运算的结果没问题，但是这个算法的效率低下，如果输入一长串的数，几分钟都不会出结果。所以想请教各位鱼油，有什么更好的办法来优化这个算法吗？非常感谢！

最佳答案

月排行榜 / 总排行榜

凌九霄

2018-6-19 21:58:07

import random
from functools import cmp_to_key

num = [random.randint(0, 1000) for i in range(random.randint(2, 1000))]
print("随机整数：{0}".format(num))


def bigNum(nums):
    key = cmp_to_key(lambda x, y: int(y + x) - int(x + y))
    result = '，'.join(sorted(map(str, nums), key=key)).lstrip('0')
    return result or '0'


print("最大整数： {0}".format(bigNum(num)))

跳转到最佳答案楼层

BngThea

给一种思路吧：
1 对输入的数据的首数字进行排序
2 如果首数字相同，则位数少的在前面
3 依次拼出排序后的所有数据即可

关键是感觉

根据楼上描述，C语言实现。其实写完后我发现出题人把问题给你描述复杂了。
其实就是字符串排序，从大到小，保证程序健壮性可以判断一下是否是有效的字符（ASCII 0-9）

#include "stdio.h"
#include "string.h"
void sort(char ** p){
        int i,j,k;
        for(i=0;i<3-1;i++){
                k=i;
                for(j=i+1;j<3;j++){
                        //printf("%s %s\n",*(p+k),*(p+j));
                        if(strcmp(*(p+k),*(p+j))<0){
                                k=j;
                        }        
                }
                //printf("***************\n");
                if(i-k){
                        char * t=*(p+i);
                        *(p+i)=*(p+k);
                        *(p+k)=t;
                }
        }
}
int main(int argc, char *argv[]){
        char * p[3]={"21","7","82"};
        int i;
        sort(p);

        for(i=0;i<3;i++){
                printf("%s",*(p+i));
        }
        return 0;
}

关键是感觉

#include "stdio.h"
#include "string.h"

int Strcmp(const char *p1,const char *p2){
        char c1,c2;
        do{
                c1=*p1;
                c2=*p2;
                if(c1=='-' || c1=='+'){
                        c1=1;
                }
                if(c2=='-' || c2=='+'){
                        c2=1;
                }
        }while(c1 && c1==c2);
        return c1-c2;
}
void sort(char ** p){
        int i,j,k;
        for(i=0;i<4-1;i++){
                k=i;
                for(j=i+1;j<4;j++){
                        //printf("%c %s\n",*(*(p+k)),(*(p+k)+1));
                        if(Strcmp(*(p+k),*(p+j))>0){
                                k=j;
                        }        
                }
                //printf("***************\n");
                if(i-k){
                        char * t=*(p+i);
                        *(p+i)=*(p+k);
                        *(p+k)=t;
                }
        }
}
int main(int argc, char *argv[]){
        //char * p[3]={"-21","7","82"};
        char * p[4]={"-21","7","82","1"};
        int i;
        sort(p);

        for(i=0;i<4;i++){
                printf("%s",*(p+i));
        }
        return 0;
}

凌九霄

BngThea 发表于 2018-6-19 16:57
给一种思路吧：
1 对输入的数据的首数字进行排序
2 如果首数字相同，则位数少的在前面

5,57 哪个在前面？

BngThea

凌九霄 发表于 2018-6-19 20:12
5,57 哪个在前面？

是我考虑不全了，那就判断第一位和第二位的大小

凌九霄

import random
from functools import cmp_to_key

num = [random.randint(0, 1000) for i in range(random.randint(2, 1000))]
print("随机整数：{0}".format(num))


def bigNum(nums):
    key = cmp_to_key(lambda x, y: int(y + x) - int(x + y))
    result = '，'.join(sorted(map(str, nums), key=key)).lstrip('0')
    return result or '0'


print("最大整数： {0}".format(bigNum(num)))

凌九霄

关键是感觉 发表于 2018-6-19 17:32
根据楼上描述，C语言实现。其实写完后我发现出题人把问题给你描述复杂了。
其实就是字符串排序，从大到小 ...

试试 char *P[3] = {"21","2","82"}

久疤K

我也来试试:

>>> def tol(s,n):
        s = s * (n//len(s)+1)
        s = s[:n]
        return s

>>> tol('123',5)
'12312'
>>> def fun( ls ):
        ls = [str(x) for x in ls]
        m = max(len(x) for x in ls)
        ls = sorted(ls, key=lambda x:tol(x,m), reverse=True)
        return int(''.join(ls))

>>> fun([5,57])
575
>>> fun([5,53])
553
>>>