剑指 Offer 45 把数组排成最小的数

    
        标签：
        
            剑指 Offer
        
    发布于：2022-02-26 21:35:39
    编辑于：2022-02-26 23:14:39
    浏览量：1032

概述

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