把数组排成最小的数
把数组排成最小的数
http://www.nowcoder.com/questionTerminal/8fecd3f8ba334add803bf2a06af1b993
题目的主要信息：
- 有一个数字中全部都是非负整数
- 将其随意拼接后要使拼接后的数字整体最小
- 返回这个最小数字的字符串形式
举一反三：
学习完本题的思路你可以解决如下题目：
方法一：重载比较的排序（推荐使用）
知识点：排序
排序就是将一个线性数据的元素按照一定的次序进行重排，这个次序可能是递增序、也可能是递减序，还有可能是自己定义的顺序（重载），常用的方法一般有快速排序、堆排序、归并排序、冒泡排序、选择排序等。再程序中的可以使用sort函数，它是基于优化后的快速排序。
思路：
这道题呢最重要的解决怎么样组装的数字是最小的，按照什么顺序组装？如果我们能得到这个次序，直接将这个次序的数字拼接在一起就好了。
只考虑首字符的大小不可靠，但是如果字符串a拼接b的得到的数字大于b拼接a，那么肯定b应该排在a的前面，我们要就按照这样的次序将排序的比较重载就可以了。
bool cmp(string& x, string& y){
//叠加
return x + y < y + x;
}
具体做法：
- step 1：优先判断空数组的特殊情况。
- step 2：将数组中的数字元素转换成字符串类型。
- step 3：重载排序比较为字符串类型的x + y < y + x，然后进行排序。
- step 4：将排序结果再按照字符串拼接成一个整体。
图示：
Java实现代码：
import java.util.*;
public class Solution {
public String PrintMinNumber(int [] numbers) {
//空数组的情况
if(numbers == null || numbers.length == 0)
return "";
String[] nums = new String[numbers.length];
//将数字转成字符
for(int i = 0; i < numbers.length; i++)
nums[i] = numbers[i] + "";
//按照重载排序
Arrays.sort(nums, new Comparator<String>() {
public int compare(String s1, String s2) {
return (s1 + s2).compareTo(s2 + s1);
}
});
StringBuilder res = new StringBuilder();
//字符串叠加
for(int i = 0; i < nums.length; i++)
res.append(nums[i]);
return res.toString();
}
}
C++实现代码：
class Solution {
public:
//重载排序比较方式
static bool cmp(string& x, string& y){
//叠加
return x + y < y + x;
}
string PrintMinNumber(vector<int> numbers) {
string res = "";
//空数组的情况
if(numbers.size() == 0)
return res;
vector<string> nums;
//将数字转成字符
for(int i = 0; i < numbers.size(); i++)
nums.push_back(to_string(numbers[i]));
//排序
sort(nums.begin(), nums.end(), cmp);
//字符串叠加
for(int i = 0; i < nums.size(); i++)
res += nums[i];
return res;
}
};
Python实现代码：
import functools
class Solution:
def PrintMinNumber(self , numbers: List[int]) -> str:
#空数组的情况
if not numbers:
return ""
#将数字转成字符
nums = list(map(str, numbers))
#重载比较大小
cmp = lambda a, b: 1 if a + b > b + a else -1
#排序
nums.sort(key = functools.cmp_to_key(cmp))
#字符串叠加
return "".join(nums)
复杂度分析：
- 时间复杂度：，其中为数组的长度，遍历两次数组，最坏复杂度为排序
- 空间复杂度：，利用辅助数组存储字符串类型的数字
方法二：冒泡排序（扩展思路）
思路：
如果觉得重载比较的方式自己掌握不太熟练，那我们可以直接尝试冒泡排序，冒泡排序过程要求比较数组相邻位置元素的大小，我们可以改成比较数组相邻字符串拼接之后的大小。
具体做法：
- step 1：优先判断空数组的特殊情况。
- step 2：将数组中的数字元素转换成字符串类型。
- step 3：使用冒泡排序，两层遍历数组，每次比较数组相邻位置字符串拼接的大小，如果顺序拼接比逆序拼接更大，则需要交换位置。
- step 4：将排序结果再按照字符串拼接成一个整体。
Java实现代码：
import java.util.*;
public class Solution {
public String PrintMinNumber(int [] numbers) {
//空数组的情况
if(numbers == null || numbers.length == 0)
return "";
String[] nums = new String[numbers.length];
//将数字转成字符
for(int i = 0; i < numbers.length; i++)
nums[i] = numbers[i] + "";
//冒泡排序
for(int i = 0; i < nums.length - 1; i++){
for(int j = 0; j < nums.length - i - 1; j++){
String s1 = nums[j] + nums[j + 1];
String s2 = nums[j + 1] + nums[j];
//比较拼接的大小交换位置
if(s1.compareTo(s2) > 0){
String temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
StringBuilder res = new StringBuilder();
//字符串叠加
for(int i = 0; i < nums.length; i++)
res.append(nums[i]);
return res.toString();
}
}
C++实现代码：
class Solution {
public:
string PrintMinNumber(vector<int> numbers) {
string res = "";
//空数组的情况
if(numbers.size() == 0)
return res;
vector<string> nums;
//将数字转成字符
for(int i = 0; i < numbers.size(); i++)
nums.push_back(to_string(numbers[i]));
//冒泡排序
for(int i = 0; i < nums.size() - 1; i++){
for(int j = 0; j < nums.size() - i - 1; j++){
string s1 = nums[j] + nums[j + 1];
string s2 = nums[j + 1] + nums[j];
//比较拼接的大小交换位置
if(s1 > s2)
swap(nums[j], nums[j + 1]);
}
}
//字符串叠加
for(int i = 0; i < nums.size(); i++)
res += nums[i];
return res;
}
};
Python实现代码：
class Solution:
def PrintMinNumber(self , numbers: List[int]) -> str:
#空数组的情况
if not numbers:
return ""
#将数字转成字符
nums = list(map(str, numbers))
#冒泡排序
for i in range(len(nums) - 1):
for j in range(len(nums) - i - 1):
s1 = nums[j] + nums[j + 1]
s2 = nums[j + 1] + nums[j]
#比较拼接的大小交换位置
if s1 > s2:
temp = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = temp
#字符串叠加
return "".join(nums)
复杂度分析：
- 时间复杂度：，其中为数组的长度，冒泡排序最坏遍历两层数组
- 空间复杂度：，利用辅助数组存储字符串类型的数字
