剑指offer45 把数组排成最小的数-Toy模板网

这篇具有很好参考价值的文章主要介绍了剑指offer45 把数组排成最小的数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接

链接

剑指offer45 把数组排成最小的数,日常算法,C++,算法,leetcode,贪心算法

其实这道题，大概看完就知道是一个排序的问题，无非就是数组中的元素以一个合适的位置排好序，这样从头加到尾，组成的整体数字最小！(题目中也暗示你排序问题了)

个人捉摸了一会，这道题能很好地锻炼仿函数的编写规则和库函数sort()的配套使用，还有就是巧妙地字符串操作和贪心思想，因此将它记录;

解法1，调用sort()

解题思路

核心: 怎么确定元素a，b的先后顺序？

贪心思想: 先将a，b两数字转成string，之后如果a+b<b+a**，那么**a就排在b前面，以此类推；

最终将排好序的每个数组转string全部从头到尾按顺序拼接即可;

实现代码

#include <string>
class Solution {
public:
    class cmp{
        public:
        bool operator()(int a,int b)
        {
            //先分别转正string
            string sa = to_string(a);
            string sb = to_string(b);
            
            return sa+sb<sb+sa;       
        }
    };
    string PrintMinNumber(vector<int> numbers) {
        //处理空串
        if(numbers.size()==0) return "";
        //按照贪心仿函数规则，调用sort
        sort(numbers.begin(),numbers.end(),cmp());

        //依次拼接最终答案
        string ret;
        for(auto&e:numbers){
            ret+=to_string(e);
        }
        return ret;
    }
};

这里要注意的点是我们调用库函数sort()，那么注意他的仿函数比较大小的规则:

源码如下:

剑指offer45 把数组排成最小的数,日常算法,C++,算法,leetcode,贪心算法

less<int>递增,如1,2,3,4,5: 仿函数源码: return a<b;

greater<int>递减,如5,4,3,2,1: 仿函数源码: return a>b;

调用sort()想要递增or递减完全是按照大于号或者小于号的方向指示的;

解法2，冒泡排序的扩展

可万一面试官突然不让你算法sort()函数了呢?不慌，贪心思想都想出来了，无非就是手撕一个排序嘛，量元素比较的时候套用我们的贪心思想比较即可!

实现代码

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
       //处理空串
        if(numbers.size()==0) return "";
        
		string res;
        //冒泡排序
        for(int i = 0; i < numbers.size() - 1; i++){
            for(int j = 0; j < numbers.size() - i - 1; j++){
                //数字转string好贪心处理
                string s1 = to_string(numbers[j]);
                string s2 = to_string(numbers[j+1]);
                
                //贪心比较拼接的大小交换位置
                if(s1+s2 > s2+s1)
                    swap(numbers[j], numbers[j + 1]);
            }
        }
        //字符串叠加返回
        for(int i = 0; i < numbers.size(); i++)
            res += to_string(numbers[i]);
        return res;
    }
};