题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

题目分析

先从题目出发,算一下给出的算例就可以发现规律,0-9当中越是小的数越应该放到最低位,数组中所有数最高位最小的应该放到前边作为高位,如果高位相同,比较下一位. 接下来从剩下的数当中依次执行这个规律,直观的想就是一个排序,但是这里面两数比较有点不太一样,关键是如何表达这种规律

可能你想到这很类似字符串的比较,有必要回顾下这个知识点:

s1与s2的大小取决于[1]:

1.如果 字符串1的第n位的ASCII码值 等于 字符串2的第n位的ASCII码值

则 继续比较下一位

2.如果 字符串1的第n位的ASCII码值 大于 字符串2的第n位的ASCII码值

则 输出结果:1,表示字符串1 > 字符串2;

3.如果 字符串1的第n位的ASCII码值 小于 字符串2的第n位的ASCII码值

则 输出结果:-1 表示字符串1 < 字符串2;

4.如果 每一位的ASCII码值都相等,而且长度相同,

则 输出结果:0 表示字符串1 == 字符串2;

5.如果 字符串1是字符串2的前m位,例如 abcd 与abcdef 比较,

则 字符串1<字符串2.

很明显第五条和我们想要的不太一样,实际上我们只需要比较的时候让字符串大小相同就可以,怎么办?拼起来:

如果$ab < ba$ , 那么$a <b$, 只需重载这个操作符然后排序,一切搞定

代码

class Solution {public:    string PrintMinNumber(vector
    
      numbers) {      string s = ""; //quickSort(numbers, 0, numbers.size()-1);        sort(numbers.begin() , numbers.end() , smaller);      for(auto i : numbers)        s+= to_string(i);      return s;    }     bool smaller(const int &s1 ,const int &s2){       string x =to_string(s1)+to_string(s2);       string y =to_string(s2)+to_string(s1);       return x
    

如果你想手敲一个快速排序的话也可以,顺便练练手,毕竟面试常考:

void quickSort(vector
    
      &a, int l , int r){     int i = l, j = r;     if(i < j){        int key = a[i];       while(i < j){        while(i
    

[1]