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

Tag: 剑指-Offer Posted on 2022-02-26 21:35:39 Edited on 2022-02-26 23:14:39 Views: 151

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/