剑指 Offer 45. 把数组排成最小的数

剑指 Offer 45. 把数组排成最小的数 - 力扣（LeetCode）

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

思路：

---

1. 一个简易的判断是 str1+str2 < str2+str1 则str1“小于”str2 反之亦反

复杂度：

O（nlogn）快排复杂度

题解：

1. 内置函数

class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> strs;
        string res;
        for(int i = 0; i < nums.size(); i++)
            strs.push_back(to_string(nums[i]));
        sort(strs.begin(), strs.end(), [](string& x, string& y){ return x + y < y + x; });
        //注意内置函数的使用语法
        for(int i = 0; i < strs.size(); i++)
            res.append(strs[i]);
        return res;
    }
};

2. 改写sort函数逻辑

   class Solution {
   public:
       string minNumber(vector<int>& nums) {
           vector<string> strs;
           for(int i = 0; i < nums.size(); i++)
               strs.push_back(to_string(nums[i]));
           quickSort(strs, 0, strs.size() - 1);
           string res;
           for(string s : strs)
               res.append(s);
           return res;
       }
   private:
       void quickSort(vector<string>& strs, int l, int r) {
           if(l >= r) return;
           int i = l, j = r;
           while(i < j) {//没看懂。。之后复习sort写法的时候再来看
               while(strs[j] + strs[l] >= strs[l] + strs[j] && i < j) j--;
               while(strs[i] + strs[l] <= strs[l] + strs[i] && i < j) i++;
               swap(strs[i], strs[j]);
           }
           swap(strs[i], strs[l]);
           quickSort(strs, l, i - 1);
           quickSort(strs, i + 1, r);
       }
   };