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

redleafage

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


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

代码如下：

1. #Users python3
   
2. __Author__ = 'Redleafage Zhang'
   
3. import sys
   
4. import itertools
   
5. from operator import itemgetter
   
6. 
   
7. def largest_number(a):
   
8.     temp= itertools.permutations(a, int(n))
   
9.     list = []
   
10. 
    
11.     # write your code here
    
12.     for i in temp:
    
13.         tempstr = ""
    
14.         for j in i:
    
15.             tempstr += j
    
16.         list.append(tempstr)
    
17.     res = max(list)
    
18. 
    
19.     return res
    
20. 
    
21. 
    
22. if __name__ == '__main__':
    
23.     input = sys.stdin.read()
    
24.     data = input.split()
    
25.     n = data[0]
    
26.     a = data[1:]
    
27.     print(largest_number(a))
    
28. 
    
29. 
    

复制代码

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

最佳答案

月排行榜 / 总排行榜

凌九霄

2018-6-19 21:58:07

1. import random
   
2. from functools import cmp_to_key
   
3. 
   
4. num = [random.randint(0, 1000) for i in range(random.randint(2, 1000))]
   
5. print("随机整数：{0}".format(num))
   
6. 
   
7. 
   
8. def bigNum(nums):
   
9.     key = cmp_to_key(lambda x, y: int(y + x) - int(x + y))
   
10.     result = '，'.join(sorted(map(str, nums), key=key)).lstrip('0')
    
11.     return result or '0'
    
12. 
    
13. 
    
14. print("最大整数： {0}".format(bigNum(num)))

复制代码

跳转到最佳答案楼层

BngThea

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

关键是感觉

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

1. #include "stdio.h"
   
2. #include "string.h"
   
3. void sort(char ** p){
   
4.         int i,j,k;
   
5.         for(i=0;i<3-1;i++){
   
6.                 k=i;
   
7.                 for(j=i+1;j<3;j++){
   
8.                         //printf("%s %s\n",*(p+k),*(p+j));
   
9.                         if(strcmp(*(p+k),*(p+j))<0){
   
10.                                 k=j;
    
11.                         }       
    
12.                 }
    
13.                 //printf("***************\n");
    
14.                 if(i-k){
    
15.                         char * t=*(p+i);
    
16.                         *(p+i)=*(p+k);
    
17.                         *(p+k)=t;
    
18.                 }
    
19.         }
    
20. }
    
21. int main(int argc, char *argv[]){
    
22.         char * p[3]={"21","7","82"};
    
23.         int i;
    
24.         sort(p);
    
25. 
    
26.         for(i=0;i<3;i++){
    
27.                 printf("%s",*(p+i));
    
28.         }
    
29.         return 0;
    
30. }
    

复制代码

关键是感觉

1. #include "stdio.h"
   
2. #include "string.h"
   
3. 
   
4. int Strcmp(const char *p1,const char *p2){
   
5.         char c1,c2;
   
6.         do{
   
7.                 c1=*p1;
   
8.                 c2=*p2;
   
9.                 if(c1=='-' || c1=='+'){
   
10.                         c1=1;
    
11.                 }
    
12.                 if(c2=='-' || c2=='+'){
    
13.                         c2=1;
    
14.                 }
    
15.         }while(c1 && c1==c2);
    
16.         return c1-c2;
    
17. }
    
18. void sort(char ** p){
    
19.         int i,j,k;
    
20.         for(i=0;i<4-1;i++){
    
21.                 k=i;
    
22.                 for(j=i+1;j<4;j++){
    
23.                         //printf("%c %s\n",*(*(p+k)),(*(p+k)+1));
    
24.                         if(Strcmp(*(p+k),*(p+j))>0){
    
25.                                 k=j;
    
26.                         }       
    
27.                 }
    
28.                 //printf("***************\n");
    
29.                 if(i-k){
    
30.                         char * t=*(p+i);
    
31.                         *(p+i)=*(p+k);
    
32.                         *(p+k)=t;
    
33.                 }
    
34.         }
    
35. }
    
36. int main(int argc, char *argv[]){
    
37.         //char * p[3]={"-21","7","82"};
    
38.         char * p[4]={"-21","7","82","1"};
    
39.         int i;
    
40.         sort(p);
    
41. 
    
42.         for(i=0;i<4;i++){
    
43.                 printf("%s",*(p+i));
    
44.         }
    
45.         return 0;
    
46. }
    

复制代码

凌九霄

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

5,57 哪个在前面？

BngThea

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

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

凌九霄

1. import random
   
2. from functools import cmp_to_key
   
3. 
   
4. num = [random.randint(0, 1000) for i in range(random.randint(2, 1000))]
   
5. print("随机整数：{0}".format(num))
   
6. 
   
7. 
   
8. def bigNum(nums):
   
9.     key = cmp_to_key(lambda x, y: int(y + x) - int(x + y))
   
10.     result = '，'.join(sorted(map(str, nums), key=key)).lstrip('0')
    
11.     return result or '0'
    
12. 
    
13. 
    
14. print("最大整数： {0}".format(bigNum(num)))

复制代码

凌九霄

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

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

久疤K

我也来试试:

1. >>> def tol(s,n):
   
2.         s = s * (n//len(s)+1)
   
3.         s = s[:n]
   
4.         return s
   
5. 
   
6. >>> tol('123',5)
   
7. '12312'
   
8. >>> def fun( ls ):
   
9.         ls = [str(x) for x in ls]
   
10.         m = max(len(x) for x in ls)
    
11.         ls = sorted(ls, key=lambda x:tol(x,m), reverse=True)
    
12.         return int(''.join(ls))
    
13. 
    
14. >>> fun([5,57])
    
15. 575
    
16. >>> fun([5,53])
    
17. 553
    
18. >>>

复制代码