题解 | #把数组排成最小的数#

分享一下我设计排序算法的思路。(3ms)
三条规则优先级自上而下：
#1 从最高位按位相比，出现不同数字时使数字小的在前： 如123>323
//很好理解，我们希望让更小的数在前
#2 位数不同时，用首位作为缺省位数： 如25（2）>253、65（6）>659
//能进行到这一轮比较的都是至少首位相同的数，用自己的首位补位即模拟用另一个数放在自己后方
#3 补齐缺省位后依然相等时，使实际末位更小的在前： 如121>12(1)、98（9）>989
//#1一样的逻辑，我们希望小的放在前

struct MG1over
{
    int num,first = -1,last = -1;//数字本身、首位、末位
    stack <int> list;//从栈顶到栈底依次保存高位到低位
};

bool cmp(MG1over m1,MG1over m2)
{
    while(!m1.list.empty() && !m2.list.empty())//#1
    {
        m1.last = m1.list.top();//记录最后数值
        m2.last = m2.list.top();
        if(m1.last!=m2.last)
        {
            return m1.last < m2.last;
        }
        m1.list.pop();
        m2.list.pop();
    }

    while(!m1.list.empty())//#2，两个#2实际上只会进入一个
    {
        m1.last=m1.list.top();
        if(m1.last!=m2.first)
        {
            return m1.last<m2.first;
        }
        m1.list.pop();
    }
    while(!m2.list.empty())//#2
    {
        m2.last=m2.list.top();
        if(m2.last!=m1.first)
        {
            return m1.first<m2.last;
        }
        m2.list.pop();
    }

    return m1.last<m2.last;//#3
}

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        vector<MG1over> elm;
        for(int i=0;i<numbers.size();i++)//将numbers中的每个元素处理加工后置于elm中
        {
            struct MG1over temp;
            temp.num = numbers[i];
            while(numbers[i])//栈中自顶向下依次为该数从高位到低位；
            {
                temp.list.push(numbers[i]%10);//低位先进栈
                numbers[i]/=10;
            }
            temp.first = temp.list.top();//记录该数首位用于补位
            elm.push_back(temp);
        }

        sort(elm.begin(),elm.end(),cmp);//begin/end为指针，front/back为对象

        string ans;//注意要求返回string类型
        for(int i=0;i<elm.size();i++)
        {
            stack<int>temp;//用一个栈将数字从高到低推入ans
            while(elm[i].num)
            {
                temp.push(elm[i].num%10);
                elm[i].num/=10;
            }

            while(!temp.empty())
            {
                ans.push_back(temp.top()+'0');
                temp.pop();
            }
        }

        return ans;
    }
};