LeetCode-剑指面试45-把数组排成最小的数-创新互联

我们可以使用C++的内置函数，先将所有数组转换成字符串进行排序后再进行输出。在此我们进行排序的逻辑是：若s1 + s2 构成的字符串的值小于 s2 + s1 构成的字符串的值，则将s1排在s2前面。我们将数组排序后统计加入字符串中即可。

class Solution {public:
    static bool cmp(string s1, string s2) {return s1 + s2< s2 + s1;
    }

    string minNumber(vector&nums) {vectornum;
        string res;
        for (int i: nums) {num.emplace_back(to_string(i));
        }
        sort(num.begin(), num.end(), cmp);
        for (string s: num) {res += s;
        }
        return res;
    }
};

除了使用内置函数之外，我们还可以自己实现快排。

class Solution {public:
    string minNumber(vector& nums) {vectorstrs;
        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& strs, int l, int r) {if(l >= r) return;
        int i = l, j = r;
        while(i< j) {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);
    }
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧