[LeetCode]Beautiful Arrangement II

这一题不要我们求排列的数量了，只需要我们求一个符合要求的排列即可。我们有n个数，那么我们可以很轻易知道k的范围，1 <= k <= n -1。k为1的情况就是递增或者递减排列即可，那么n - 1的情况怎么排呢。假设我们第一个排1，那么下一个数只能取n，之后的数只能取2，以此类推。也就是说当k = n - 1的时候，我们有且只有一种排法，那就是依次从收尾取数。k > n -1的话不可能存在符合要求的排列，那么对于k < n - 1的情况，我们只要取前k + 1个数进行依次取收尾的排列，这样我们已经有了k个不同的的差的绝对值，剩下的数，我们递减或者递增排列保证差的绝对值是1即可，这样排完后仍然满足要求。时间复杂度O(n)，常数空间，代码如下：

	class Solution {
	public:
	vector<int> constructArray(int n, int k) {
	if(n < k + 1)return {};
	vector<int> res(n, 0);
	int i = 1, j = k + 1;
	while(i < j)
	{
	res[k + 1 - (j - i + 1)] = i;
	++i;
	res[k + 1 - (j - i + 1)] = j;
	--j;
	}
	if(i == j)
	res[k] = i;
	for(int i = k + 1; i < n; ++i)
	res[i] = i + 1;
	return res;
	}
	};

view raw Beautiful Arrangement II.cpp hosted with ❤ by GitHub