[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)，常数空间，代码如下：