一、题目
题目描述
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
示例1:
示例2:
1 2
| 输入: [3,30,34,5,9] 输出: "3033459"
|
二、分析
1.方法1:暴力组合法
我们可能下意识会想到用DFS求组合的方法,将所有情况暴力枚举出来。然后再比较得到最小的组合方法。
时间复杂度:组合O(n!)+ 比较O(n)
空间复杂度:O(n)
时间复杂度太高,此方法是下策,所以我们暂时不考虑用此种方法。
2.方法2:排序法
此题难点就是考虑将其转换成排序问题。题目要求的是数组组合成最小的数,问题就是如何将数组组合才能使其最小。
我们定义了一种排序规则:
1 2
| x,y是数组两个数。如果组合xy<yx,那么x<y x,y是数组两个数。如果组合yx<xy,那么y<x
|
定义了该规则后,将整个数组从小到大排序就能得到数组最小数组合了。
三、代码
1.自己写快排(自己造轮子)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
|
string minNumberA(vector<int>& nums) { QuikSortA(0, nums.size() - 1, nums); string res; for (int i : nums) { res.append(to_string(i)); } return res; } bool myCompare(int a, int b) { return to_string(a) + to_string(b) < to_string(b) + to_string(a); } int partitionA(vector<int>& nums, int first, int last) { int privot = nums[first]; while (first < last) { while (first < last && !myCompare(nums[last], privot)) { --last; } nums[first] = nums[last]; while (first < last && myCompare(nums[first], privot)) { ++first; } nums[last] = nums[first]; } nums[first] = privot; return first;
} void QuikSortA(int low, int high, vector<int>& nums) { if (low >= high)return; int mid = partitionA(nums, low, high); QuikSortA(low, mid - 1, nums); QuikSortA(mid + 1, high, nums); }
|
2.利用内置函数实现排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
|
string minNumberB(vector<int>& nums) { string res; sort(nums.begin(), nums.end(), [](const int& a, const int& b)->bool { return to_string(a) + to_string(b) < to_string(b) + to_string(a); }); for (auto i : nums) res.append(to_string(i)); return res; }
|
四、总结
此题核心是知道怎么转换成排序问题。