剑指offer45把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例1：

输入: [10,2]
输出: "102"

示例2：

输入: [3,30,34,5,9]
输出: "3033459"

我们可能下意识会想到用DFS求组合的方法，将所有情况暴力枚举出来。然后再比较得到最小的组合方法。

时间复杂度：组合O(n！)+ 比较O(n)

空间复杂度：O(n)

时间复杂度太高，此方法是下策，所以我们暂时不考虑用此种方法。

此题难点就是考虑将其转换成排序问题。题目要求的是数组组合成最小的数，问题就是如何将数组组合才能使其最小。

我们定义了一种排序规则：

x,y是数组两个数。如果组合xy 
定义了该规则后，将整个数组从小到大排序就能得到数组最小数组合了。
 
三、代码 
1.自己写快排（自己造轮子） 
	
	string minNumberA(vector& 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& 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& nums) {
		if (low >= high)return;
		int mid = partitionA(nums, low, high);
		QuikSortA(low, mid - 1, nums);
		QuikSortA(mid + 1, high, nums);
	}
 
2.利用内置函数实现排序 
	
	string minNumberB(vector& 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;
	}
 
四、总结 
此题核心是知道怎么转换成排序问题。