首页 > 试题广场 >

把数组排成最小的数

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

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

输入

[11,3]

输出

"113"
示例2

输入

[]

输出

""
示例3

输入

[3,32,321]

输出

"321323"
算法知识视频讲解
查看答案及解析
添加回答
灰空头像 灰空
排列为最小数组的思路：将整数列表转换为字符串列表，按照排序规则
 * 若ab > ba 则 a > b，b排前
 * 若ab < ba 则 a < b，a排前
 * 若ab = ba 则 a = b，
的规则排序字符串，最后连接字符串转换为整数。 
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if not numbers or numbers == []:
            return ''
        tmpNumbers = sorted(numbers,cmp=self.compare)
        return int(''.join(map(str,tmpNumbers)))
    
    def compare(self,numb1,numb2):
        t = str(numb1) + str(numb2)
        s = str(numb2) + str(numb1)
        if t == s:
            return 0
        if t < s:
            return -1
        else:
            return 1

发表于 2019-05-30 10:07:15 回复(0)
更多回答
推荐
飞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
华科平凡头像 华科平凡

python solution:

# -*- coding:utf-8 -*-
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 '0' if numbers[0]=='0' else ''.join(numbers)

经过@zhejiangblue提醒， 最后一行写的有问题，最终改成：

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).lstrip('0') or'0'

```

编辑于 2018-03-27 08:19:42 回复(34)
碗碗头像 碗碗 
class Solution {
public:
    static bool compare( const string &st1,const string &st2){
        string s1 = st1+st2;
        string s2 = st2+st1;
        return s1<s2;
    }
    string PrintMinNumber(vector<int> numbers) {
         string result;
        if(numbers.size()<=0){
            return result;
        }
        vector<string> strNum;
        for(int i=0;i<numbers.size();i++ ){
           stringstream ss;
            ss<<numbers[i];
            string s = ss.str();
            strNum.push_back(s);
        }
        sort(strNum.begin(),strNum.end(),compare);
       
        for(int i=0;i<strNum.size();i++){
            result.append(strNum[i]);
        }
        return result;
        
    }
};

发表于 2015-06-14 17:36:35 回复(19)
已注销头像 已注销 
class Solution {
public:
    //如果题目要求得出最大的数字，可以将比较器转换成从大到小排序即可
   //其中，数字转化为字符串的使用方法，参考别人的代码%>_<%
 static int compare(const string& st1,const string& st2)
    {
        string s1=st1+st2;
        string s2=st2+st1;
        return s1<s2;//降序排列，改为大于就是升序排列！！！
    }
    string PrintMinNumber(vector<int> numbers) {
        string result;
        if(numbers.size()<=0) return result;
        vector<string> vec;
        for(unsigned int i=0;i<numbers.size();i++)
        {
            stringstream ss;//使用输入输出流，头文件要包含#include<sstream>
            ss<<numbers[i];//读入数字给流处理
            string s = ss.str();//转换成字符串
            vec.push_back(s);//将字符串s压入vec中
        }
        //排序，传入比较器，从小到大排序
        sort(vec.begin(),vec.end(),compare);
        for(unsigned int i=0;i<vec.size();i++)
        {
            result.append(vec[i]);//拼接字符串，这就是最小的数字
        }
        return result;
    }
};

编辑于 2016-07-29 16:47:19 回复(7)
马客(Mark)头像 马客(Mark) 


string itos(int x){
    return (x > 9 ? itos(x / 10) : "") + char(x % 10 + '0');
}
bool cmp(int a, int b){
    return itos(a) + itos(b) < itos(b) + itos(a);
}
class Solution {
public:
    string PrintMinNumber(vector<int> a) {
        sort(a.begin(), a.end(), cmp);
        string s = "";
        for(int i = 0; i < int(a.size()); ++i) s += itos(a[i]);
        return s;
    }
};

发表于 2015-08-23 02:33:15 回复(4)
drdr头像 drdr 
class Solution {
public:
    string PrintMinNumber(vector<int> numbers){
        string ret;
        vector<string> numbers_str;
        for(int i = 0; i < numbers.size(); ++i)
            numbers_str.push_back(to_string(numbers[i]));        
        sort(numbers_str.begin(), numbers_str.end(), MyCompare);
        for(int i = 0; i < numbers_str.size(); ++i)
            ret += numbers_str[i];        
        return ret;
    }
private:
    static bool MyCompare(const string &str1, const string &str2){
		return str1 + str2 < str2 + str1;
    }
};

发表于 2017-05-24 14:42:38 回复(2)
Duqcuid头像 Duqcuid 
// 利用lambda的简洁解法
import java.util.*;
public class Solution {
    public String PrintMinNumber(int [] numbers) {
        String[] strs = new String[numbers.length];
        for(int i = 0; i < numbers.length; i++)
            strs[i] = String.valueOf(numbers[i]);
        return Arrays.stream(strs)
                    .sorted((x, y) -> (x + y).compareTo(y + x))
                    .reduce("", (x, y) -> x + y);
    }
}

发表于 2018-03-17 15:10:04 回复(3)
C/C++
卷积神经网络哦头像 卷积神经网络哦 
class Solution {
public:
    static bool cmp(int x, int y){
        return to_string(x) + to_string(y) < to_string(y) + to_string(x);
    }

    string PrintMinNumber(vector<int> numbers) {
        sort(numbers.begin(), numbers.end(), cmp);
        string ans = "";
        for(int i = 0; i < numbers.size(); i++) 
            ans += to_string(numbers[i]);
        return ans;
    }
};
发表于 2018-12-09 15:24:35 回复(2)
JavaScript
汕大小吴头像 汕大小吴
JS又来啦啦啦
主要就是定义新的排序规则，也就是把前一个数和后一个数拼接起来的数，然后再与后一个数和前一个数拼接起来的数比较字典序 
function PrintMinNumber(numbers)
{
    numbers.sort(function(s1,s2){
        let c1=s1+""+s2;
        let c2=s2+""+s1;
        return c1>c2;
    });
    let min="";
    numbers.forEach(i=>min+=i)
    return min;
}

发表于 2018-04-08 01:31:11 回复(3)
Java
小烈111头像 小烈111
java流处理，两行解决 
import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        List<String> s = Arrays.stream(numbers).mapToObj(c -> c + "").sorted((o1, o2)->(o1 + o2).compareTo(o2 + o1)).collect(Collectors.toList());
        return s.stream().collect(Collectors.joining());
    }
}



发表于 2020-03-20 23:18:23 回复(3)
JavaScript
Niuke_Li头像 Niuke_Li 
function PrintMinNumber(numbers)
{
    return numbers.map(x=>x+'').sort((a,b)=>(a+b)-(b+a)).join('')
}
js 大法好, 一行就搞定
编辑于 2019-02-12 01:57:58 回复(1)
C/C++
牛客吴彦祖QAQ头像 牛客吴彦祖QAQ

bool compare(int m, int n) //定义sort中的比较规则
{
string mn = to_string(m) + to_string(n);
string nm = to_string(n) + to_string(m);
if(strcmp(mn.c_str(), nm.c_str()) > 0) //m>n
return false;
else
return true;
}

class Solution
{
public:
string PrintMinNumber(vector numbers)
{
string ret;
if(numbers.size() == 0)
return ret;
sort(numbers.begin(), numbers.end(), compare);
for(int i = 0; i < numbers.size(); i++)
{
ret = ret + to_string(numbers[i]);
}
return ret;
}

};

编辑于 2017-05-22 22:12:17 回复(0)
Java
jackpiggy头像 jackpiggy 
package com.code.offer;

import java.util.*;

/**
 * Created by jiangchao on 2016/10/9.
 */
public class Solution32 {
    public String PrintMinNumber(int [] numbers) {
       if (numbers == null || numbers.length == 0) return "";
       MyComparator myComparator = new MyComparator();
        List<Integer> list = new ArrayList<Integer>();
        for (int i : numbers) {
            list.add(i);
        }
        Collections.sort(list, myComparator);
        StringBuilder sb = new StringBuilder();
        for (Integer val : list) {
            sb.append(val);
        }
        return sb.toString();
    }

    private class MyComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            String s1 = String.valueOf(o1);
            String s2 = String.valueOf(o2);
            String str1 = s1+s2;
            String str2 = s2+s1;
            return str1.compareTo(str2);
        }
    }
}

发表于 2016-10-09 12:51:32 回复(1)
老石基头像 老石基 
import java.util.ArrayList;

import java.util.ArrayList;

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        if(numbers==null||numbers.length==0)
            return "";
        if(numbers.length==1)
            return ""+numbers[0];
		String[] str = new String[numbers.length];
        
        for(int i = 0;i<numbers.length;i++){
            str[i] = ""+numbers[i];
        }
        sort(str);
        StringBuffer sb = new StringBuffer();
        for(int i = 0;i<str.length;i++){
            sb.append(str[i]);
        }
        return sb.toString();
    }
    
    private void sort(String[] s){
        for(int i = 0;i<s.length-1;i++){
            boolean flag = true;
            for(int j = 0;j<s.length-i-1;j++){
                if((s[j]+s[j+1]).compareTo(s[j+1]+s[j])>0){
                    String t = s[j+1];
                    s[j+1] = s[j];
                    s[j] = t;
                    flag = false;
                }
            }
            if(flag)
                return;
        }
        
    }
}

发表于 2016-04-18 23:29:56 回复(1)
Python
The_Flash头像 The_Flash
import itertools
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        res = []
        if len(numbers) == 0:
            return ""
        for i in itertools.permutations(numbers):
            temp = 0
            for x in i:
                temp = temp * (10**len(str(x))) + x
            res.append(temp)
        return min(res)
发表于 2018-04-20 04:12:43 回复(0)
Java
together"头像 together"
Java最简洁做法： 
import java.util.*;

public class Solution {
    public String PrintMinNumber(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return "";
        }
        Integer[] nums = Arrays.stream(numbers).boxed().toArray(Integer[]::new);
        Arrays.sort(nums, (o1, o2) -> ("" + o1 + o2).compareTo("" + o2 + o1));
        StringBuilder sb = new StringBuilder();
        for (int num : nums) {
            sb.append(num);
        }
        return sb.toString();
    }
}


发表于 2021-09-19 11:00:44 回复(0)
OOMError头像 OOMError

根据最高票答案，改成JDK1.8，简洁易懂。

public String PrintMinNumber(int [] numbers) {
        ArrayList<Integer> list = new ArrayList();
        Arrays.stream(numbers).forEach(list::add);

        list.sort((str1, str2) -> {
            String s1 = str1 + "" + str2;
            String s2 = str2 + "" + str1;
            return s1.compareTo(s2);
        });

        String s = "";
        for (int j : list) {
            s += j;
        }

        return s;
    }
编辑于 2019-06-20 20:45:57 回复(0)
Python
顧左头像 顧左 
    def PrintMinNumber(self, numbers):
        if numbers == []:
            return ""
        else:
            numbers = [str(i) for i in numbers]
            numbers.sort(cmp = lambda x,y : int(x+y)-int(y+x))
            return int(''.join(numbers))

发表于 2017-07-11 17:12:48 回复(2)
spursKawhi头像 spursKawhi 
public class Solution {
    public String PrintMinNumber(int[] numbers) {
        if(numbers.length == 0 || numbers == null) return "";
        
        int j;
        for(int i = 1; i < numbers.length; i++) {
            int t = numbers[i];
            for(j = i; j > 0 && compare(t, numbers[j-1]) < 0; j--)
                numbers[j] = numbers[j-1];
            numbers[j] = t;
        }
        
        String result = "";
        for(int e:numbers)
            result += e;
        return result;
    }
    
    private int compare(int a, int b) {
        String s1 = "" + a + b;
        String s2 = "" + b + a;
        return s1.compareTo(s2);
    }
}

编辑于 2016-06-12 12:53:23 回复(1)
萌头像 萌 
class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
  if (numbers.empty())
  {
   return string();
  }
  string res;
  vector<string> strNum(numbers.size());
  for (size_t i = 0; i < numbers.size(); i++)
  {
   stringstream ss;
   ss << numbers[i];
   strNum[i].append(ss.str());
  }
  sort(strNum.begin(), strNum.end(), [=](string a, string b) {
   string s1 = a + b;
   string s2 = b + a;
   return s2 > s1;
  });
  for (int i = 0; i<strNum.size(); i++) {
   res.append(strNum[i]);
  }
  return res;


 }
};



                                                                                    



                                        

                                            
                                                                                                                                                            发表于  2016-07-29 17:13:14
                                                    
                                                                                            
                                                回复(0)
                                                                                                                                            

                                        

                                


                                                                                                                            
                                                                

                                


                                    

                                                                                
                                        
                                        
                                                                            


                                    


                                        

                                                                                                                                    乒乓头像
                                            乒乓
                                        



                                        

                                                                                            
/*对vector容器内的数据进行排序，按照 将a和b转为string后 
 若 a＋b<b+a  a排在在前 的规则排序,
 如 2 21 因为 212 < 221 所以 排序后为 21 2  
  to_string() 可以将int 转化为string
*/ class Solution {
 public:
     static bool cmp(int a,int b){
         string A="";
         string B="";
         A+=to_string(a);
         A+=to_string(b);
         B+=to_string(b);
         B+=to_string(a);
         
         return A<B;
     }
     string PrintMinNumber(vector<int> numbers) {
         string  answer="";
         sort(numbers.begin(),numbers.end(),cmp);
         for(int i=0;i<numbers.size();i++){
             answer+=to_string(numbers[i]);
         }
         return answer;
     }
 };



                                                                                    



                                        

                                            
                                                                                                                                                            发表于  2016-08-29 22:44:05
                                                    
                                                                                            
                                                回复(68)
                                                                                                                                            

                                        

                                


                                                            
                        

                        
                                        

                            

        


                    

                                    

                        

                            

                            

                                提交观点
                            

                        

                    

                            

            

    

          

            
问题信息

            

              

                                      贪心
                                      数组
                                      排序
                                

                                  

                
                                                            

                                        难度：

                                

                                        1150条回答
                      
                      157539浏览
                                

            

          


                        

  

    

      
      
      
    

    
热门推荐

  

  

    

      
    

  



            

                

            

          
                          

                

                  
通过挑战的用户

                                          查看代码
                                    

                

                  
                

              

            
                          

                
相关试题

                

                  
                

              

            
                            

                        把数组排成最小的数
                

                





                
        

                                                                

        

    
    
    

    


            
    
    

        

            

                
            

            
扫一扫，把题目装进口袋

        

        

            
求职之前，先上牛客

            

                
                    

                        

                        

                            
                            
扫描二维码，进入QQ群

                        

                    

                
                
                    

                        

                        

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