题目链接

题意

题目意思如题，简单明了。

题解

此题本质上就是一个排序问题。为什么能看成一个排序问题呢？
因为对于当前的任意两个数字，a+b>b+a，则说明数字b要放在a的后面组成的数才更大，那么也就是b>a。这与我们对自然数排列大小时，大的数字排在后面一致。（那么上面所述其实就是针对此问题的排序规则大小的重新定义）
那么这里以快速排序这一具体排序算法为例进行分析，选取好标志位之后，我要做的就是把这个数组中放在我前面组成的数更小的都排到我前面，这个数字比放到我后面更大的数字都放到我后面。而针对放在我前面的数该怎么排，就是下一轮的事了。当前轮只有做到这样，才不会发生别的数字跟当前标志位变换位置从而产生更小的数的情况发生。

代码实现

  1. class Solution {
  2. public:
  3.     string minNumber(vector<int>& nums) {
  4.         vector<string> strs;
  5.         for (int i = 0; i < nums.size(); i++) {
  6.             strs.push_back(to_string(nums[i]));
  7.         }
  8.         quickSort(strs, 0, strs.size() - 1);
  9.         string res;
  10.         for (string s : strs) {
  11.             res.append(s);
  12.         }
  13.         return res;
  14.     }
  15. private:
  16.     void quickSort(vector<string>& strs, int l, int r) {
  17.         if (l >= r) return;
  18.         int st = l, ter = r;
  19.         //对于该题就是相当于重新定义排序规则
  20.         while (st < ter) {
  21.             while (strs[ter] + strs[l] >= strs[l] + strs[ter] && st < ter) ter--;
  22.             while (strs[st] + strs[l] <= strs[l] + strs[st] && st < ter) st++;
  23.             swap(strs[st], strs[ter]);
  24.         }
  25.         swap(strs[l], strs[st]);
  26.         //快排的递归
  27.         quickSort(strs, l, st-1);
  28.         quickSort(strs, st + 1, r);
  29.     }
  30. };