首页 > 试题广场 >

把数组排成最小的数

[编程题]把数组排成最小的数
  • 热度指数：518104 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
输入一个非负整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。
1.输出结果可能非常大，所以你需要返回一个字符串而不是整数
2.拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

数据范围:
0<=len(numbers)<=100
示例1

输入

[11,3]

输出

"113"
示例2

输入

[]

输出

""
示例3

输入

[3,32,321]

输出

"321323"
算法知识视频讲解
添加回答
推荐
飞dsadsadasd头像 飞dsadsadasd

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        int n;
  String s="";
  ArrayList<Integer> list= new ArrayList<Integer>();
  n=numbers.length;
  for(int i=0;i<n;i++){
   list.add(numbers[i]);
   
  }
  Collections.sort(list, new Comparator<Integer>(){
  
  public int compare(Integer str1,Integer str2){
   String s1=str1+""+str2;
   String s2=str2+""+str1;
         return s1.compareTo(s2);
     }
  });
  
  for(int j:list){
   s+=j;
  }
        return s;

    }
}

编辑于 2015-06-19 17:37:53 回复(89)
Python
LYC_ley头像 LYC_ley 
# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        res = []
                #冒泡排序
        n = len(numbers)
        tmp = 0
        numbers = sorted(numbers)
        for i in range(n-1):
            for j in range(i+1,n):
                if str(numbers[i]) + str(numbers[j]) > str(numbers[j]) + str(numbers[i]):
                    numbers[j],numbers[i] = numbers[i],numbers[j]
        a = list(map(str,numbers))
        return "".join(a)
         说白了就是排序，不管是是快排还是冒泡，只要str之后的两两对比，小的在前面就好了   

发表于 2021-08-21 15:10:10 回复(0)
Python
nixiaoyu头像 nixiaoyu
我神奇了，我想了另一种方法，就是把位数都填充成一样的来比较，如[3, 32, 321]，填成[333,322,321]，排序，再把排序后的原数组拼接起来。只是这个排序需要自己写，因为要保存indices（应该也有库函数可实现）。这个方法提交通过了，但是挺奇怪的哈哈，不知道有没有问题呢。 
# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if len(numbers) == 0:
            return ''
        
        # 填充位数
        max_n = max(numbers)
        max_fi = len(str(max_n))
        filled_numbers = []
        indices = []
        i = 0
        for x in numbers:
            strx = str(x)
            while len(strx) < max_fi:
                strx += strx[-1]
            filled_numbers.append(strx)
            indices.append(i)
            i += 1

        # 排序
        for i in range(len(numbers)):
            for j in range(i):
                if filled_numbers[j] > filled_numbers[i]:
                    tmp = filled_numbers[i]
                    filled_numbers[i] = filled_numbers[j]
                    filled_numbers[j] = tmp
                    tmpi = indices[i]
                    indices[i] = indices[j]
                    indices[j] = tmpi

        # 最后拼接
        new_numbers = [numbers[i] for i in indices]
        final = ''
        for x in new_numbers:
            strx = str(x)
            final += strx


        return final
    


发表于 2021-07-07 21:56:25 回复(0)
Python
牛客541273514号头像 牛客541273514号 
# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if not numbers:
            return ''
        n=len(numbers)
        str_numbers=[]
        for i in range(n):
            s=str(numbers[i])
            str_numbers.append(s)
        res=''
        while str_numbers:
            out=str_numbers[0]
            l=len(str_numbers)
            for i in range(1,l):
                out=self.compare(out,str_numbers[i])
            out_index=str_numbers.index(out)
            str_numbers=str_numbers[:out_index]+str_numbers[out_index+1:]
            res+=out
        return res
    def compare(self,str1,str2):
        if str1+str2<str2+str1:
            return str1
        else: return str2

发表于 2021-04-22 01:03:45 回复(0)
Python
Hiroi头像 Hiroi
Python 先写出所有组合（用字符串，结果是int），然后取最小值，特殊情况是空。 
# -*- coding:utf-8 -*-
class Solution:
    def PrintAll(self,numbers):
        results = []
        for i in range(len(numbers)):
            temp1 = str(numbers[i])
            temp2 = numbers[:]
            temp2.pop(i)
            if len(temp2):
                temp3 = self.PrintAll(temp2)
                for num in temp3:
                    results.append(int(temp1+str(num)))
            else:
                results.append(int(temp1))
        return results
#       
    def PrintMinNumber(self, numbers):
        # write code here
        allnum = self.PrintAll(numbers)
        if len(allnum):
            output = str(min(allnum))
        else:
            output = ''
        return output
        


发表于 2021-04-17 19:59:00 回复(0)
Python
Lucifer201头像 Lucifer201
class Solution:
    def PrintMinNumber(self, numbers):
        #  思路：排序数组，重定义排序方法，使用堆排序，输出结果
        #  定义比较方法
        def lt(s1, s2):
            return True if s1+s2 < s2+s1 else False
        def change(arr, root, end):
            child = root*2+1
            while child <= end:
                if child+1<=end and lt(arr[child], arr[child+1]):
                    child+=1
                if lt(arr[root], arr[child]):
                    arr[root], arr[child] = arr[child], arr[root]
                    root = child
                    child = root*2+1
                else:
                    break
        #  堆排序
        def heap_sort(arr):
            start = len(arr) // 2 -1
            for i in range(start, -1, -1):
                change(arr, i, len(arr)-1)
            for end in range(len(arr)-1, 0, -1):
                arr[0], arr[end] = arr[end], arr[0]
                change(arr, 0, end-1)

        # write code here
        if not numbers:
            return ""
        for i in range(len(numbers)):
            numbers[i] = str(numbers[i])
        heap_sort(numbers)
        return "".join(numbers)
发表于 2021-03-19 23:50:37 回复(0)
Python
在下小6头像 在下小6

python解法：

# -*- coding:utf-8 -*-
'''
解法1:选择数字最高位最小的放前面，转换成字符串好做一点，类似排序的做法；
排序是直接比较两者大小，这个是根据a+b>b+a判断；
s=list(map(str, numbers))可以把所有数字转换成字符串存入到s中；
'''
class Solution:
    def PrintMinNumber(self, numbers):
        res = []
        for i in range(len(numbers)-1):
            for j in range(i+1,len(numbers)):
                # 每次选择数字最高位最小的放前面
                if str(numbers[i]) + str(numbers[j]) > str(numbers[j]) + str(numbers[i]):
                    numbers[i],numbers[j] = numbers[j],numbers[i]
        res = ''.join(str(i) for i in numbers)
        return res
发表于 2021-02-19 11:39:49 回复(0)
Python
zhd要到160斤头像 zhd要到160斤 
# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        
        for i in range(1,len(numbers)):
            for j in range(0,len(numbers)-i):
                s1 = ''.join(str(x) for x in numbers[j:j+2])
                s2 = ''.join(str(y) for y in numbers[j:j+2][::-1])
                if s1 > s2:
                    numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
        return ''.join(str(x) for x in numbers)
冒泡排序的变形 基本思路都不变，就是比较的东西变了
发表于 2020-11-28 10:43:52 回复(0)
Python
在下萝莉控ii老公头像 在下萝莉控ii老公
clean python 
class Solution:
    def PrintMinNumber(self, numbers):
        if not numbers: return ''
        numbers = ''.join(sorted(map(str, numbers), cmp = lambda x, y: cmp(x+y, y+x)))
        return '0' if numbers[0] == '0' else numbers


发表于 2020-11-11 22:41:36 回复(0)
Python
12313242头像 12313242
穷举法的简化版本 
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        for i in range(len(numbers)):
            for j in range(i+1,len(numbers)):
                a = int(str(numbers[i])+str(numbers[j]))
                b = int(str(numbers[j])+str(numbers[i]))
                if a > b:
                    numbers[i], numbers[j] = numbers[j], numbers[i]
        return ''.join(list(map(str, numbers)))


编辑于 2020-10-30 00:42:13 回复(0)
Python
锐捷网络-招聘头像 锐捷网络-招聘 
# -*- coding:utf-8 -*-
"""
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，
打印能拼接出的所有数字中最小的一个
"""
import itertools   #使用模块产生可迭代对象
class Solution(object):
    def PrintMinNumber(self, numbers):
        # write code here
        assert len(numbers)>0 #
        lis = []
        for l in list(itertools.permutations(numbers)):#全排列迭代成元组
            str0 = [str(i) for i in l] #l为元组类型转换成字符列表str0
            l = ''.join(str0) #将字符数字连接成整体字符串
            lis.append(int(l))#将字符l转换成整型存入到lis列表中
        return min(lis)#返回lis列表中的最小值

发表于 2020-09-20 17:05:48 回复(0)
Python
BJ-2020头像 BJ-2020

思路：
1:转化为字符串比较
2:比较函数重新写，mn < nm则m , n位置不变
3:如果不熟悉sort，就自己写一个快排就行

import functools
class Solution:
    def PrintMinNumber(self, numbers):
        # write code hereif not numbers: return ""
        if not numbers: return ""
        number = list(map(str, numbers))
        number.sort(key=functools.cmp_to_key(self.compare))
        return "".join(number).lstrip('0') or'0'
    def compare(self,num1, num2):
        m = str(num1) + str(num2)
        n = str(num2) + str(num1)
        if m > n:
            return 1
        elif m == n:
            return 0
        else:
            return -1
发表于 2020-09-11 16:48:57 回复(0)
Python
火树银花zjl头像 火树银花zjl 
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if not numbers:
            return ""
        numbers=list(map(str,numbers))
        numbers.sort(cmp = lambda x, y:cmp(x+y,y+x))
        return "".join(numbers)
这是python用法
发表于 2020-08-28 11:34:30 回复(0)
Python
jianlinp头像 jianlinp
要比较两个数谁应该放在前面，应该从最高位比起，如果相同，则比较次高位。如果位数少的与位数多的数比较，则应该自动补足位数少的数，补足的方法是不断循环重复自己，直到与最大的数的位数相同为止。 
# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        if not numbers:
            return ""
        # write code here
        # 找到最大数，确定是几位数
        m = max(numbers)
        k = 0
        s = m/10
        while s:
            k += 1
            s = s / 10
        door = 10**k
        
        def tr(n):
            # 将一个数按照从左到右转换成各个位阶上的数组
            s = n
            ds = []
            while s:
                k = s /10
                r = s % 10
                ds.append(r)
                s = k
            ds = ds[::-1]
            d = len(ds)
            # 循环重复自己，补齐到与最大的数的位数相同，返回补齐后的数，自己的位数
            i = 0
            while n < door:
                n = n * 10 + ds[i]
                i = (i+1) % d
            return n, d
        # 按照补齐以后的数进行排序，小的在前面
        new = sorted(numbers, key=lambda x: tr(x)[0])
        # 将排序好的数组组装成一个大的整数
        degrees = map(lambda x: tr(x)[1], new)
        total = sum(degrees)
        re = 0
        for e, d in zip(new, degrees):
            total -= d
            re += e * (10**total)
        return re

发表于 2020-06-10 01:16:00 回复(0)
Python
一直爬的蜗牛头像 一直爬的蜗牛 
# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if len(numbers) == 1:
            return numbers

        res = {}
        for i, v in enumerate(numbers):
            res[i] = v

        max_num = max(res.values())
        ml = len(str(max_num))

        result = {}
        for k,v in res.items():
            if len(str(v)) < ml:
                result[k] = str(v) + "9"*(ml-len(str(v)))
            else:
                result[k] = str(v)

        result = sorted(result.items(),key=lambda x:x[1])

        minNum = ""
        for i in result:
            minNum += str(res[i[0]])

        return int(minNum)
虽然我知道这种解法不对，但是挺好玩的贴上来。一会儿再贴
发表于 2020-05-24 00:57:46 回复(1)
Python
牛客124928456号头像 牛客124928456号
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        import itertools
        number=map(str,numbers)
        result=[]
        if not numbers:
            return ""
        else:
            res=itertools.permutations(number)
            for i in res:
                if "".join(i) not in result:
                    result.append("".join(i))
        return min(map(int,result))
发表于 2020-05-21 19:04:01 回复(0)
Python
Sandy头像 Sandy
用快排来对numbers进行排序，判断条件从以前的a<b变成str(a)+str(b)<str(b)+str(a) 
class Solution:
    def PrintMinNumber(self, numbers):
        numbers = self.quick(numbers)
        s = ''
        for i in numbers:
            s+=str(i)
        return s

    def quick(self, numbers, key=0):
        if not numbers:
            return []
        if len(numbers)==1:
            return numbers
        n = len(numbers)
        left, right = [], []
        for i in range(1,n):
            if str(numbers[i])+str(numbers[key])>str(numbers[key])+str(numbers[i]):
                right.append(numbers[i])
            else:
                left.append(numbers[i])
        return self.quick(left)+[numbers[key]]+self.quick(right)


发表于 2020-03-15 22:29:14 回复(1)
Python
刘摇滚头像 刘摇滚
python一行解法： 
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
         return "".join(str(i) for i in sorted(numbers,key=cmp_to_key(lambda a, b: -1 if str(a)+str(b)<str(b)+str(a) else 1)))

发表于 2020-02-28 22:27:57 回复(0)
Python
黄沙遮天头像 黄沙遮天 
# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        (727)# write code here
        length=len(numbers)
        if length==0:
            return ''
        number=[str(i) for i in numbers]
        for i in range(length-1):
            for j in range(length-2,i-1,-1):
                #将数组内的数字进行两两比较进行排序，然后再拼接就是最小的含多数字的数
                if int(number[j]+number[j+1])>int(number[j+1]+number[j]):
                    number[j],number[j+1]=number[j+1],number[j]
        num=''.join(number)
        return num
本题的重点就是获得最小的一个全排列，我们发现两两数字拼接的规则可以通过自反，对称，传递性传到n个数字的拼接。因此我们只需要两两比较，确定一个“最小的”排序数组就行了，此时将所有进行拼接，就能得到最小的
发表于 2020-02-20 20:22:05 回复(0)
Python
andycruz头像 andycruz
Python 解法
不够位数的补齐比较即可 
class Solution:
    def PrintMinNumber(self,numbers):
        if not numbers:
            return ''
        maxl = len(str(max(numbers)))
        tmp = [str(x) for x in numbers]
        for i in range(len(tmp)):
            while len(tmp[i]) < maxl:
                tmp[i] += tmp[i][-1]
        tmp = [int(x) for x in tmp]
        zlist = list(zip(tmp,numbers))
        zlist = sorted(zlist, key = lambda x:x[0])
        res = ''
        for i in zlist:
            res += str(i[1])
        return res.lstrip('0')&nbs***bsp;0


编辑于 2020-02-20 02:00:23 回复(0)
Python
不想再被拒头像 不想再被拒 
# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        def Perm(start_index):
            if start_index >= len(char_numbers):
                clone = "".join(char_numbers)
                result.append(clone)
            else:
                swap_index = start_index
                while swap_index < len(char_numbers):
                    char_numbers[swap_index], char_numbers[start_index] = char_numbers[start_index], char_numbers[swap_index]
                    Perm(start_index+1)
                    char_numbers[swap_index], char_numbers[start_index] = char_numbers[start_index], char_numbers[swap_index]
                    swap_index += 1

        result = []
        char_numbers = [str(num) for num in numbers]
        Perm(0)
        return min(result)
全排序实现
发表于 2020-02-11 14:21:43 回复(0)
提交观点

问题信息

贪心 数组 排序
难度：
95条回答 153413浏览

热门推荐

通过挑战的用户

查看代码

相关试题

把数组排成最小的数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号