nc85. 拼接所有的字符串产生字典序最小的字符串

1. 思路一: (利用stl)

要想产生字典序最小的字符串, 只需尽量把字典序小的往前放. 所以我们进行一次排序, 将字典序小的排到前面.

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

实现如下:

class Solution {
public:
    /**
     * 
     * @param strs string字符串vector the strings
     * @return string字符串
     */
    static bool cmp(const string &a, const string &b) {
        return (a+b) < (b+a); // 如上面描述, 不能直接比a<b, 否则会wa
    }
    string minString(vector<string>& strs) {
        // 使用stl的排序
        sort(strs.begin(), strs.end(), cmp);
        // 排序后的数组连接起来即可
        string res;
        for (auto a : strs) {
            res += a;
        }
        return res;
    }
};
  • 时间复杂度: 若strs数组的长度为n, 因为进行了一轮排序, 所以整体的时间复杂度是 O(nlogn).
  • 空间复杂度: 没有使用额外空间, 故空间复杂度是O(1).

思路二: 自己写快排

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

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

图片说明

那么, 祭出我们的快速排序模板吧!

class Solution {
public:
    /**
     * 
     * @param strs string字符串vector the strings
     * @return string字符串
     */
    static bool cmp(const string &a, const string &b) {
        return (a+b) <= (b+a); 
        // 这里需要注意, 要写成小于等于, 因为排序的时候, 如果遇到了相等的情况, 会出现tle, 原因是第18行的while一直不会出去
    }

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

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

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

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

    string minString(vector<string>& strs) {
        int n = strs.size();
        quicksort(strs, 0, n-1); // 对数组strs排序
        string res;
        for (auto a : strs) {
            res += a;
        }
        return res;
    }
};
  • 时间、空间复杂度同思路一