剑指 Offer 62. 圆圈中最后剩下的数字思路推导（约瑟夫环、DP、递归）

一、题目

剑指 Offer 45. 把数组排成最小的数

题目描述

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

示例1：

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

示例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.自己写快排（自己造轮子）

/*
* 题目：剑指 Offer 45. 把数组排成最小的数
* 描述：
* 方法：定义判断规则，任意两个字符串如果有xy<yx，那么x就应该放在前面，然后用快速排序
* 实现:
*/
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.利用内置函数实现排序

/*
* 题目：剑指 Offer 45. 把数组排成最小的数
* 描述：
* 方法：同上，用内置函数sort实现快速排序
* 实现:
*/
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;
}