AlgoPressAppearance
45-把数组排成最小的数
题目描述
https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
提示:
0 < nums.length <= 100
说明:
- 输出结果可能非常大，所以你需要返回一个字符串而不是整数
- 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
思路分析
基本思路，按照前置位排序
排序完成后，按次序输出
这道题的难点在与找到一个自定义的 比较大小的方式
如果 直接比较两个数字，从首位开始比较，则较难处理字符串，这一步考虑太复杂了
其实 题目要求两个数字拼接后的最小值，那么直接 拼接 [num1][num2] 和 [num2][num1] 比较字符串大小即可
实现代码
csharp
public class Solution {
private bool LargeThan(int num1, int num2){
string str1 = num1.ToString();
string str2 = num2.ToString();
string s1 = str1+str2;
string s2 = str2+str1;
for(int i = 0; i < s1.Length; i++){
if(s1[i] != s2[i]){
return s1[i] > s2[i];
}
}
return false;
}
public string MinNumber(int[] nums) {
for(int i=0; i<nums.Length-1; i++){
for(int j=i+1; j<nums.Length; j++){
if(LargeThan(nums[i],nums[j])){
//swap
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
}
//输出
string result = "";
for(int i=0;i < nums.Length; i++){
result += nums[i].ToString();
}
return result;
}
}
思路2：SortedSet错误
使用 SortedSet 按照字母序列将数组加入，然后按照顺序输出结果 测试用例 [3,30] 不通过，会返回 330 而不是 303，数字 3 排在了 30 前面 错误原因：SortedSet按照字符串排序，3 排在了30之前，不符合题意
csharp
public class Solution {
public string MinNumber(int[] nums){
SortedSet<string> s = new SortedSet<string>();
for(int i=0; i<nums.Length; i++){
s.Add(nums[i].ToString());
}
StringBuilder sb = new StringBuilder();
foreach(var num in s){
sb.Append(s);
}
return sb.ToString();
}
}
思路3
定义
csharp
public class Solution {
public string MinNumber(int[] nums) {
//自定义按照字符顺序排序
Array.Sort(nums, (a,b)=>{
return (a+""+b+"").CompareTo(b+""+a+"");
});
StringBuilder sb = new StringBuilder();
for(int i=0; i<nums.Length; i++){
sb.Append(nums[i].ToString());
}
return sb.ToString();
}
}