剑指 Offer 45 把数组排成最小的数
概述
https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
贪心法
每次优先选择首字符小的那个,如果有两个相同,则比较后面的。
对于缺位的要如何比较呢?此时应选择剩余可选的中最小首字符补位。
一个想法是把所有值补位到相同长度,对于需要补位的数字,我们按顺序为其补位。
比较麻烦,就不写了吧。
排序法
对于两个数字 m 和 n,拼起来的方式为 mn 和 nm,通过比较这两个值我们就能得到 m 和 n 的优先级顺序, 据此对所有数字进行排序,进而再进行拼接。
如果需要考虑溢出问题,我们可以使用字符串进行比较:
class Solution {
public:
string minNumber(vector<int>& nums) {
vector<string> strs;
for (auto num : nums) strs.push_back(to_string(num));
sort(strs.begin(), strs.end(), [](const string& a, const string& b) -> bool {
return a + b < b + a;
});
string ans;
for (auto& str : strs) ans += str;
return ans;
}
};
Links: sword-offer-45