首页 > 试题广场 > 把数组排成最小的数
[编程题]把数组排成最小的数
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。
推荐

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 回复(71)
/*对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 回复(43)
 * 解题思路:
 * 先将整型数组转换成String数组,然后将String数组排序,最后将排好序的字符串数组拼接出来。关键就是制定排序规则。
 * 排序规则如下:
 * 若ab > ba 则 a > b,
 * 若ab < ba 则 a < b,
 * 若ab = ba 则 a = b;
 * 解释说明:
 * 比如 "3" < "31"但是 "331" > "313",所以要将二者拼接起来进行比较
public String PrintMinNumber(int [] numbers) {
		if(numbers == null || numbers.length == 0) return "";
		int len = numbers.length;
		String[] str = new String[len];
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < len; i++){
			str[i] = String.valueOf(numbers[i]);
		}
		Arrays.sort(str,new Comparator<String>(){
			@Override
			public int compare(String s1, String s2) {
				String c1 = s1 + s2;
				String c2 = s2 + s1;
				return c1.compareTo(c2);
			}
		});
		for(int i = 0; i < len; i++){
			sb.append(str[i]);
		}
		return sb.toString();
    }

发表于 2015-10-03 14:48:09 回复(42)
一开始觉得暴力解开可以吧,但是觉得这是零分的做法就没有这样做,但是在讨论区里看大家的回答我好像连看的冲动都没有(是我眼力太差...),于是自己想啊想。排序脑子里只有排序,怎么排?感觉是看每个数字的最高位排序,降序,然后其他位上再降序,其中考虑长度,想着想着做着越想越做越乱,实在受不了于是百度了一下,没看别人的代码(http://blog.csdn.net/fanzitao/article/details/7895344),只是看一下解析,比较关键的一句话 所以在这里自定义一个比较大小的函数,比较两个字符串s1, s2大小的时候,先将它们拼接起来,比较s1+s2,和s2+s1那个大,如果s1+s2大,那说明s2应该放前面,所以按这个规则,s2就应该排在s1前面。 ,突然大悟。
public class Solution {
    public String PrintMinNumber(int [] numbers) {
        String str = "";
		for (int i=0; i<numbers.length; i++){
			for (int j=i+1; j<numbers.length; j++){
				int a = Integer.valueOf(numbers[i]+""+numbers[j]);
				int b = Integer.valueOf(numbers[j]+""+numbers[i]);
				if (a > b){
					int t = numbers[i];
					numbers[i] = numbers[j];
					numbers[j] = t;	
				}
				
			}
		}
		for (int i = 0; i < numbers.length; i++) {
			str += String.valueOf(numbers[i]);
		}
		return str;
    }
}


发表于 2017-07-17 23:05:35 回复(64)
//more about lambda,you can reference:http://blog.csdn.net/taoyanqi8932/article/details/52541312
class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {  
        sort(numbers.begin(),numbers.end(),[](const int& a,const int& b){ 
        return to_string(a)+to_string(b)<to_string(b)+to_string(a);});
        string res;
        for (auto c:numbers)    
    		res+=to_string(c);
        return res;
    }
};

编辑于 2016-10-09 19:38:12 回复(12)
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 回复(18)

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 回复(24)
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 回复(4)


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)
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)
#Python版
#使用自定义的排序方法
#
# -*- coding:utf-8 -*-
class Solution:
    def compare(self,num1,num2):
        t = str(num1)+str(num2)
        s = str(num2)+str(num1)
        if t>s:
            return 1
        elif t<s:
            return -1
        else:
            return 0

    def PrintMinNumber(self, numbers):
        # write code here
        if numbers is None:
            return ""
        lens = len(numbers)
        if lens ==0 :
            return ""
        tmpNumbers = sorted(numbers,cmp=self.compare)
        return int(''.join(str(x)for x in tmpNumbers))

print Solution().PrintMinNumber([3,32,321])

编辑于 2016-12-05 19:21:22 回复(2)
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)
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 回复(2)
// 利用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 回复(2)
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)
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)

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)
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)
萌头像
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)

根据最高票答案,改成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)
function PrintMinNumber(numbers)
{
    return numbers.map(x=>x+'').sort((a,b)=>(a+b)-(b+a)).join('')
}

js 大法好, 一行就搞定
编辑于 2019-02-12 01:57:58 回复(1)