Leetcode-667

发表于 | 分类于

题目

  题目描述如下：

  • 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]
  • Example 2:
    Input: n = 3, k = 2
    Output: [1, 3, 2]

分析

  看到这道题的时候，一开始的出发点不正确。我先尝试了n=1~7的各种情况，我的初步判断是为一个动态规划问题，因为欲得到k=m的情况，必先得到k=m-1的情况，然后从后一种情况经过调整变为前一种情况。实践证明，这样解并不是一个很明智的选择，因为这样定义的步骤虽然有规律，但是描述起来比较困难，并且计算机的时间复杂度较高

求解

  实现参考“Solution”的思路。一个符合k=m要求的数组可以用两部分组成，第一部分的两项间的差恒定为1，第二部分的二项间的差满足从差的绝对值从2-m。
  我们发现当k=1的时候，数组仅需要按自然数排列即可；对于长度为n的情况，当k=n-1的时候。满足条件的数组为[1,n,2,n-1,3,n-2,….]。利用这两条规律。结合第一段的解题思路即可完成本题。具体实现如下：
  当输入为n,k的时候，我们将1-n的数组分为两个部分，第一部分为1-(n-k+1),其间距为1；第二部分按照[1,k+1,2,k,3,k-1,….]+(n-k+1)进行赋值，可以保证第二部分的间距为2-k。因为第一部分的结尾与第二分部的开头的差值为1,不会影响两个部分的效果。代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] constructArray(int n, int k) {
        int[] ans = new int[n];
        int c = 0;
        for (int v = 1; v < n-k; v++) {
            ans[c++] = v;
        }
        for (int i = 0; i <= k; i++) {
            ans[c++] = (i%2 == 0) ? (n-k + i/2) : (n - i/2);
        }
        return ans;
    }
}

  Complexity Analysis
   Time Complexity: $O(n)$
   Space Complexity: $O(n)$