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

1. 将数组进行排序，排序的原则是对于数字a和b，如果ab<ba，则a在b前。

2. 将数组中的元素连起来即可。

注意计算ab和ba过程中的性能优化，避免重复计算，包括指数运算和求位数，也可以选择性能高的排序算法。

int g_tenPow[] = 
{
    0, 
    10, 
    100, 
    1000, 
    10000, 
    100000, 
    1000000, 
    10000000, 
    100000000, 
    1000000000,
};

class Solution {
public:
    int calcDecimalLen(int n)
    {
        int cnt = 1;
        while (n /= 10)
        {
            cnt++;
        }

        return cnt;
    }
    
    map<int, int> calcDecimalLen(const vector<int> &numbers)
    {
        map<int, int> lenMap;
        for (int i = 0; i < numbers.size(); i++)
        {
            lenMap[numbers[i]] = calcDecimalLen(numbers[i]);
        }

        return lenMap;
    }
    
    bool lessThan(map<int, int> &lenMap, int x, int y)
    {
        int xLen = lenMap[x];
        int yLen = lenMap[y];
        int x_y = x * g_tenPow[yLen] + y;
        int y_x = y * g_tenPow[xLen] + x;

        if (x_y < y_x)
            return true;

        return false;
    }
    
    void sort(vector<int> &numbers)
    {
        map<int, int> lenMap = calcDecimalLen(numbers);
        
        for (int i = 0; i < (int)numbers.size() - 1; i++)
        {
            for (int j = i + 1; j < numbers.size(); j++)
            {
                if (!lessThan(lenMap, numbers[i], numbers[j]))
                {
                    swap(numbers[i], numbers[j]);
                }
            }
        }
    }
    
    string PrintMinNumber(vector<int> numbers) {
        string ret;
        sort(numbers);
        for (int i = 0; i < numbers.size(); i++)
        {
            char str[20] = {0};
            sprintf(str, "%d", numbers[i]);
            ret += str;
        }

        return ret;
    }
};