n个整数组合成最大数问题(python表达)
本帖最后由 redleafage 于 2018-6-19 16:28 编辑题目要求：输入N个整数，自动求出这n个整数能组成的最大数。
比如输入：
3（表示一共有多少个整数）
21 7 82
则直接输出：82721
我的思想是：
1.求出输入的整数的所有可能出现的排列组合，组成一个新列表。
如输入1，2，求出的列表即为：[,]
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
a = data
print(largest_number(a))
整个运算的结果没问题，但是这个算法的效率低下，如果输入一长串的数，几分钟都不会出结果。所以想请教各位鱼油，有什么更好的办法来优化这个算法吗？非常感谢！ 给一种思路吧：
1 对输入的数据的首数字进行排序
2 如果首数字相同，则位数少的在前面
3 依次拼出排序后的所有数据即可 本帖最后由 关键是感觉 于 2018-6-19 17:33 编辑
根据楼上描述，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={"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={"-21","7","82"};
char * p={"-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 哪个在前面？ 凌九霄 发表于 2018-6-19 20:12
5,57 哪个在前面？
是我考虑不全了，那就判断第一位和第二位的大小 本帖最后由 凌九霄 于 2018-6-19 22:07 编辑
import random
from functools import cmp_to_key
num =
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 = {"21","2","82"} 我也来试试:
>>> def tol(s,n):
s = s * (n//len(s)+1)
s = s[:n]
return s
>>> tol('123',5)
'12312'
>>> def fun( ls ):
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()
575
>>> fun()
553
>>>
页:
[1]