剑指Offer45.把数组排成最小的数 C++

1、题目描述

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: “102”
示例 2:
输入: [3,30,34,5,9]
输出: “3033459”

2、VS2019上运行

先转换成字符串再组合起来

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>using namespace std;class Solution {
public:// 将整数数组组合成最小的字符串string minNumber(vector<int>& nums) {vector<string> strs;  // 存储转换后的字符串string ans;  // 存储最终结果for (int i = 0; i < nums.size(); i++) {strs.push_back(to_string(nums[i]));  // 将整数转换为字符串并添加到向量中}// 使用自定义的比较函数对字符串向量进行排序sort(strs.begin(), strs.end(), [](string& s1, string& s2) {return s1 + s2 < s2 + s1;});// 将排序后的字符串依次拼接到最终结果中for (int i = 0; i < strs.size(); i++) {ans += strs[i];}return ans;  // 返回最小的组合数结果}
};int main() {Solution solution;vector<int> nums = { 3, 30, 34, 5, 9 };  // 示例输入string result = solution.minNumber(nums);cout << "Minimum Combination: " << result << endl;  // 输出最小的组合数return 0;
}

Minimum Combination: 3033459

3、解题思路

• 1.定义了一个 Solution 类，其中的 minNumber 函数接收一个整数向量 nums 作为参数，并返回一个字符串。
• 2.在 minNumber 函数中，首先创建一个字符串向量 strs 用于存储将整数转换为字符串后的结果，以及一个空字符串 ans 用于存储最终的结果。
• 3.使用 for 循环遍历整数向量 nums，将每个整数转换为字符串，并将转换后的字符串添加到 strs 向量中。
• 4.使用自定义的比较函数作为参数传递给 sort 函数，对 strs 向量进行排序。该比较函数的逻辑是通过拼接两个字符串 s1 和 s2，并比较拼接后的结果 s1+s2 和 s2+s1 的大小，如果 s1+s2 小于 s2+s1，则 s1 排在 s2 前面。
• 5.排序完成后，通过 for 循环将排序后的字符串依次拼接到 ans 字符串中。
• 6.最终将 ans 字符串作为函数的返回结果，即为最小的组合字符串。
• 7.在主函数中，创建一个 Solution 类的对象 solution，并示例化一个整数向量 nums。
• 8.调用 solution 的 minNumber 函数，并将结果赋给字符串 result。
• 9.通过 cout 输出最小的组合字符串。
• 该算法的关键思路是将整数数组转换为字符串，然后利用自定义的比较函数对字符串进行排序，最后将排序后的字符串进行拼接得到最小的组合。这种比较函数的构造方法可以确保拼接得到的字符串是最小的。

4、Lambda 函数

• 在这里，Lambda 函数定义为 [](string& s1, string& s2) { return s1 + s2 < s2 + s1; }，它接受两个字符串引用参数 s1 和 s2，并返回一个布尔值。
• Lambda 函数的逻辑是基于字符串的拼接形式来比较字符串的大小。它对 s1 和 s2 分别进行拼接，形成 s1 + s2 和 s2 + s1，然后比较两个拼接后的字符串大小。如果 s1 + s2 小于 s2 + s1，则认为 s1 小于 s2，返回 true；否则，返回 false。
• 这样，通过传递这个 Lambda 函数作为 sort 函数的比较函数参数，可以实现按照自定义规则对字符串向量进行排序。排序后，字符串向量中的字符串将按照组合后的最小值从小到大排列。
• 在 sort() 函数中使用 Lambda 函数时，不需要使用 -> 符号来指定返回类型。Lambda 表达式的返回类型可以由编译器进行自动推导，根据表达式的内容来推断返回类型。在这种情况下，由于 sort() 函数需要使用的比较函数是一个布尔函数，返回类型为 bool，因此编译器可以推断出返回类型为 bool，无需显式指定。

4、sort函数

• sort() 函数是 C++ 标准库中的一个算法函数，用于对容器中的元素进行排序。它按升序（默认）或按通过比较函数指定的排序规则对元素进行排列。
• sort() 函数的基本语法为：

template<class RandomIt>
void sort(RandomIt first, RandomIt last);template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

• 其中，first 和 last 是表示要排序的元素范围的迭代器，指定了排序范围的首尾位置。comp 是一个可选的比较函数，用于指定元素的排序规则。如果未提供比较函数，则默认使用 < 运算符进行元素的比较。sort() 函数采用的排序算法是快速排序（QuickSort）或其变种。