【每日一题】数组系列(1) —— 把数组排成最小的数

写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我热爱AI、热爱分享、热爱开源！ 这博客是我对学习的一点总结与记录。如果您也对 深度学习、机器视觉、算法、C++ 感兴趣，可以关注我的动态，我们一起学习，一起进步~
我的博客地址为：【AI 菌】的博客

1.题目

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例1：
输入: [10,2] 输出: "102"
示例2：
输入: [3,30,34,5,9] 输出: "3033459"

  

 

  
1
  
2
  
3
  
4
 

提示：

• 0 < nums.length <= 100

说明：

• 输出结果可能非常大，所以你需要返回一个字符串而不是整数
• 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.解题

2.1头脑风暴

• 简单来说，本题就是要求拼接起来的“最小值”，其实本质上还是一个排序问题。
• 考虑到是排序问题，可以直接使用快排函数sort()。但是根据题目要求，要求的是拼接起来的“最小值”，因此要改变排序判断规则。
• 由于输入的是整型数组，而拼接、输出的是字符串。因此，还要熟悉整型转字符型的
  方法。

对于上面的三个问题下面我们来一一剖析：
（1）对于基本的几种排序方法，以及相应的算法复杂度分析，了解一下还是很有必要。如果还不太了解，建议你先加加餐：【算法之美】不要再用冒泡、选择、插入排序了，丢不起这人！
（2）sort()函数是一种很常用的快排方法，不仅能节编写代码时间，而且在时间、空间复杂度上的综合指标也不错。

• 先熟悉一下sort()函数的基本用法：

在C++中，使用sort()函数前，需添加头文件：#include<algorithm>

1. 默认情况下是：从小到大排序（升序）
sort(arrNum.begin(), arrNum.end())

2.如果要从大到小排序（降序），则需要添加排序判断规则
bool compare(int a, int b){ return a>b;   //自定义判断规则
}
sort(arrNum.begin(), arrNum.end(), compare)  //降序

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

• 那么对于本题，需要如何改变判断规则，才能使拼接起来的数最小呢？我们可以先看一下这张图：

比如“3”和“30”，到底谁应该放前面？我们只需先拼接起来看一下：330 或者 303，很明显，303要小，因此要将30排前面，3放在后面。
不难理解，要使得拼接后的值最小，就要想方设法把“小数”放在前面，但是每一个数的位数不同，因此我们不能直接进行比较。这里可以用一个取巧的方法，不去比较数的每一位的大小，而是去比较前后字符串拼接后的“大小”。当数组中，每相邻元素都满足这种“大小”关系时，最后将排列后的数组元素拼接在一起就是最小值了。
那么怎么通过改变判断规则实现呢？实现方法如下：

bool compare(string s1, string s2){
	return s1+s2 < s2+s1;
}
sort(arr_str.begin(), arr_str.end(), compare)

  

 

  
1
  
2
  
3
  
4
 

补充一下字符串大小比较规则：从左往右，依次比较每个字符对应的ASCII码值，大者为大，小者为小；若相等，则继续比较后面的字符。

（3）整型转字符型

• 对于大部分编译器，支持C++11新特性，可以直接使用函数to_string()

使用前需添加头文件：#include<string>
str_num = to_string(num) //将整型数num转化成字符串str_num

  

 

  
1
  
2
 

• 对于不支持C++11的编译器（比如一些竞赛中），可使用如下方法：

使用前需添加头文件：#include<sstream>
实现整型转字符串:
string NumToString(int num){ 
	string output;
	stringstream Convert;
	Convert<<num;
	Convert>>output;
	return output;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

2.2代码实践

熟悉以上解题思路后，我们就可以编写出简单有效的代码了：

class Solution {
public:
	static bool compare(string s1, string s2){
		return s1+s2 <s2+s1; //自定义排序规则 
	} string minNumber(vector<int>& nums) { vector<string> temp; for(int n : nums){ temp.push_back(to_string(n)); //整型转字符串  } sort(temp.begin(), temp.end(), compare); //按自定义规则排序  string ans = ""; for(string s : temp) ans += s; //拼接  return ans; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

测试结果：

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/105405016