首页 > 试题广场 >

把数组排成最小的数

[编程题]把数组排成最小的数

热度指数：518049 时间限制：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"

算法知识视频讲解

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)

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

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

梦醒时分270

python solution

看了前几个回答，没想到是考察定义新的排序规则，我脑回路不太正常的想了另一个方法：

对于这道题，拿题里的样例[3,32,321]举例，首先检测数组中最大的是几位数，假设为N，然后我们只需要定义一个新数组，原数组里位数不足N位的数则在数字后面补它的首位数，比如上述数组，最大是3位数，第一个数字3的首位是3，补足后为333；32的首位是3，补足后为323，整个数组补完后变成[333,323,321]，然后对新数组按大小排序：[321,323,333]，原数组按相同索引变换排序，则变为[321,32,3]，然后直接先后组合在一起就是答案：321323。

有一点值得注意的是，第六行的"numbers = sorted(numbers)"不加也是可以通过的，但是样例里如果出现[3,323,32] 这样的情况，结果就会是错误的，需要保证补过位的数在前面。

# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        if not numbers:
            return ""
        numbers = sorted(numbers)  # 这一行不加也能过，但是最好加上
        max_number = max(numbers)
        len_max = len(str(max_number))
        new_numbers = []
        for num in numbers:
            pad = num // (10**(len(str(num))-1))
            new_num_str = num
            for i in range(len_max-len(str(num))):
                new_num_str = str(new_num_str) + str(pad)
            new_num = int(new_num_str)
            new_numbers.append(new_num)
        # 冒泡排序
        for i in range(len(new_numbers)-1):
            for j in range(len(new_numbers)-i-1):
                if new_numbers[j] > new_numbers[j+1]:
                    new_numbers[j],new_numbers[j+1] = new_numbers[j+1],new_numbers[j]
                    numbers[j],numbers[j+1] = numbers[j+1],numbers[j]
        result = ""
        for num in numbers:
            result += str(num)
        return result

编辑于 2019-08-20 21:22:20 回复(7)

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

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

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

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

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

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"

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

根据最高票答案，改成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

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)

提交观点

问题信息

贪心数组排序

难度：

1150条回答 3315收藏 153069浏览

通过挑战的用户

查看代码

noob_

2022-10-18 00:02:51
PoonCyun

2022-10-11 17:00:29
牛客59147...

2022-09-29 14:22:36
Scotty2...

2022-09-18 18:29:03
优秀的羚羊爱健身

2022-09-16 11:11:51

把数组排成最小的数

输入

输出

输入

输出

输入

输出

python solution:

问题信息

热门推荐

通过挑战的用户

相关试题