Ex45 把数组排成最小的数

题目描述

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

解题思路

这个题目的核心idea是，每两个数排在一起。例如m和n，如果mn<nm，则拼接后m应排在n前面。这个更多的是一个直觉性的想法，具体的证明可以参见《剑指Offer》书籍。

另外，转换成字符串之后，这个比较可能很好的变为字符串比较大小。

代码

class Solution
{
public:
  std::string
  minNumber (std::vector<int> &nums)
  {
    std::vector<std::string> strings;
    for (auto &num : nums)
      strings.push_back (std::to_string (num));
    std::sort (strings.begin (), strings.end (),
               [] (std::string &a, std::string &b) { return a + b < b + a; });
    return std::accumulate (strings.begin (), strings.end (), std::string{});
  }
};

结果

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了99.74%的用户

内存消耗：12.9 MB, 在所有 C++ 提交中击败了5.02%的用户