题解 | #最大数#

nc111. 最大数

题意

给你一个数组，由非负整数组成，求一个拼接方案，使得拼起来的数最大。去掉前导0

这道题和https://www.nowcoder.com/practice/f1f6a1a1b6f6409b944f869dc8fd3381 是一道题，思路完全相同，也可以参考nc85的题解。

1. 利用stl：

要想产生最大的数，等价于该数对应的字符串字典序最大。因此我们进行排序，将字典序大的数排到前面。

但是需要注意的是, 对于两个数字字符串a和b, 如果直接比较数字a和b的大小，进行排序, 这样得到的答案将是错误的. 例如: "10" 和 "1". 两个数, 如果按数字大小排, 那么10在1的前面，拼接得到的数是101, 这显然是错误的. 故我们需要对两个字符串连接后的字典序进行比较. 所以实现时, 要对a+b和b+a 比较字典序. c++语言中, 可以直接使用 < > 这样的运算符比较.

与NC85题不同的是，本题还有一个特殊情况，就是数据为全0时，不能返回"000000.....", 只能返回1个0，实现时，特判排序后数组第一个数（即最大的数）是否为0即可。

class Solution {
public:
    static bool cmp(const int &a, const int &b) {
        string s1 = to_string(a), s2 = to_string(b);
        return (s1+s2) > (s2+s1); // 如上面描述, 不能直接比a<b, 否则会wa
    }

    string solve(vector<int>& nums) {
        sort(nums.begin(), nums.end(), cmp);
        string res;
        for (auto i : nums) 
            res += to_string(i);

        // 全是0的数组会wa,特判之
        if (!nums[0]) return "0";
        return res;
    }
};

时间复杂度: 若 nums 数组的长度为n, 因为进行了一轮排序, 所以整体的时间复杂度是 $O(nlogn).$
空间复杂度: 定义了和n成正比的变量res, 因此空间复杂度为 $O(n)$ .

思路二: 自己写快排

如果面试要求不允许使用stl? 那么我们需要自己写一个排序算法. 这里以快排为例, 毕竟大多数面试官都比较爱考快排. 思路同上, 只是把sort()替换为自己实现的快排.
先复习一下快速排序的思路：

以数组[6 4 7 1 2]为例:

图片说明

class Solution {
public:
    static bool cmp(const int &a, const int &b) {
        string s1 = to_string(a), s2 = to_string(b);
        return (s1+s2) >= (s2+s1); // 如上面描述, 不能直接比a>b, 否则会wa
    }

        // quicksort 快速排序算法, 待排序区间为[start, end]
    void quicksort(vector<int> &nums, int start, int end) {
        if (start >= end) return; // 递归终点: 区间不合法(长度<=0)
        int i = start, j = end;
        int p = nums[i]; // 中轴随便取,本题中取最左边的元素

        while (i < j) {
            // 右边的字符串如果小于等于基准, 则j指针往左走
            while (i<j && cmp(p, nums[j])) j--;
            // j指针推到第一个「严格大于」基准的, 将i换过去
            nums[i] = nums[j];

            // 逻辑同上, 直到ij相遇
            // 这里如果cmp函数不写等号, 有可能ij永不相遇
            while (i<j && cmp(nums[i], p)) i++;
            nums[j] = nums[i];
        }

        // ij相遇时, 就是一轮快速排序完成, 终点赋值为中轴
        nums[i] = p;
        quicksort(nums, start, i-1);
        quicksort(nums, i+1, end);
    }

    string solve(vector<int>& nums) {
        int n = nums.size();
        quicksort(nums, 0, n-1); // 对数组strs排序
        string res;
        for (auto i : nums) 
            res += to_string(i);

        // 全是0的数组会wa,特判之
        if (!nums[0]) return "0";
        return res;
    }
};

时间、空间复杂度同思路一