Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to n and obeys the following requirement: Suppose this list is [a1, a2, a3, … , an], then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, … , |an-1 - an|] has exactly k distinct integers.
If there are multiple answers, print any of them.
Example 1:
Input: n = 3, k = 1 Output: [1, 2, 3] Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.Example 2:
Input: n = 3, k = 2 Output: [1, 3, 2] Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.Note:
The n and k are in the range 1 <= k < n <= 104.题目分析：给定n和k，要求输出一个包含1-n的序列，序列满足规律：相邻数差的绝对值得种类恰好是k个。 输出序列必然存在多个（证明：假设序列q符合题意，那么reverse(q)必然也成立）。现在假设这k个差表示的是1到k，并且相邻差的绝对值也是按照这个顺序。构造的符合题意得数列如下：
k=1: 1 2 3 4 5 6 7 k=2: 2 1 3 4 5 6 7 k=3: 2 3 1 4 5 6 7 k=4: 3 2 4 1 5 6 7 k=5: 3 4 2 5 1 6 7 …….. 规律： 1、p[0]=k/2+1; 2、deta=1到k，正负号相间 3、若k是奇数，则deta先正后负，否则先负后正。 7、以上规律持续到deta=k，即第（k+1)个位置，之后的数据顺序递增。代码如下：
class Solution { public int[] constructArray(int n, int k) { int[]result=new int[n]; int st=(k/2)+1; boolean flag=k%2==0?false:true; result[0]=st; for(int i=1;i<=k;i++){ if(flag) result[i]=result[i-1]+i; else result[i]=result[i-1]-i; flag=!flag; } for(int i=k+1;i<n;i++) result[i]=i+1; return result; } }