输入一个非负整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。
1.输出结果可能非常大，所以你需要返回一个字符串而不是整数
2.拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
2.拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
数据范围:
0<=len(numbers)<=100
[编程题]把数组排成最小的数
/*对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)
* 解题思路：
* 先将整型数组转换成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
回复(45)
//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
回复(13)
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)
#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
回复(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 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)
// 利用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)
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)
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)
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)
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)
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)
问题信息
难度：
1147条回答
3244收藏
150209浏览
通过挑战的用户
查看代码-
2022-10-18 00:02:51
-
2022-10-11 17:00:29 -
2022-09-29 14:22:36
-
2022-09-18 18:29:03
-
2022-09-16 11:11:51
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
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;
}
}