难度: Medium
原题连接
内容描述
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.
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******
想要正好有k个不同的数字，注意题目说的是k个不同的绝对值
我们发现：
- 1个不同的就是[1,2,3,4....n]
- 2个不同的就是[1,2,3,4....n-3,n-2,n,n-1]
- 3个不同的就是[1,2,3,4....n-4,n-3,n,n-2,n-1]
- ...
- ...
- n个不同的就是[1,2,3...n-k-1, 剩下最小，剩下最大，剩下第二小，剩下第二大.....]，即[1,2,3...n-k-1, n-k, n, n-k+1，n-1,.....]
beats 99.15%
class Solution(object):
def constructArray(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[int]
"""
res = [i for i in range(1, n-k)]
for i in range(k+1): # [1,2,3...n-k-1, 剩下最小，剩下最大，剩下第二小，剩下第二大.....]
cur = n - i // 2 if i & 1 else n - k + i // 2
res.append(cur)
return res