成都网站建设企业 排名,北京建设执业注册中心网站,网站开发工资,市场seo是什么意思剑指 Offer#xff08;第2版#xff09;面试题 45#xff1a;把数组排成最小的数 剑指 Offer#xff08;第2版#xff09;面试题 45#xff1a;把数组排成最小的数解法1#xff1a;排序 剑指 Offer#xff08;第2版#xff09;面试题 45#xff1a;把数组排成最小的数… 剑指 Offer第2版面试题 45把数组排成最小的数 剑指 Offer第2版面试题 45把数组排成最小的数解法1排序 剑指 Offer第2版面试题 45把数组排成最小的数
题目来源58. 把数组排成最小的数
解法1排序
两个数字 m 和 n 能拼接数字 mn 和 nm排序规则为如果 mn nm就把 m 排在 n 的前面否则把 m 排在 n 的后面。
如何拼接数字
当 m 和 n 都很大时拼接出来的数字会超过 int 能表达的范围但把它们拼接成字符串就没问题了拼接得到的 mn 和 nm 的位数一定相同因此比较它们的大小只需要按照字符串大小的比较规则即可。
代码
class Solution
{
private:static bool cmp(const int num1, const int num2){string s1 to_string(num1), s2 to_string(num2);return s1 s2 s2 s1;}public:string printMinNumber(vectorint nums){string ans;if (nums.empty())return ans;sort(nums.begin(), nums.end(), cmp);for (const int num : nums)ans to_string(num);return ans;}
};复杂度分析
时间复杂度O(nlogn)其中 n 是数组 nums 的长度。
空间复杂度O(1)。
