솔루션: 아름다운 배치 II

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #667 (중간): 아름다운 배열 II

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

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.

제약:

• The n and k are in the range 1 <= k < n <= 10^4.

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

이 문제에 대해 우리는 k에 대한 가능한 값의 범위와 일치하는 배열의 특성에 대해 생각해야 합니다. 가능한 k의 가장 작은 값은 분명히 1이며, 엄격하게 증가(또는 감소)하는 배열로 얻을 수 있습니다. 그러나 k에 대해 가능한 가장 큰 값에 대해 생각하는 것은 약간 더 어렵습니다.

먼저 배열의 값 범위인 [1, n]을 고려할 수 있습니다. 해당 범위에 있는 두 숫자의 가능한 가장 큰 절대 차이는 분명히 두 극단인 1과 n 사이의 차이(n - 1)입니다. 가능한 가장 작은 절대 차이는 분명히 1이므로 아마도 가능한 것처럼 보일 것입니다. 범위 [1, n - 1] 또는 n - 1의 k 값에서 각 차이를 달성합니다.

그러나 이것이 실제로 가능합니까?

예를 들어 n = 5 및 k = 4를 살펴보겠습니다. 4의 절대 차이를 얻을 수 있는 유일한 방법은 1과 5가 연속되는 것입니다. 그런 다음 3의 다음으로 가장 작은 절대 차이에 대해 1 & 4 또는 2 & 5인 두 가지 가능성이 있습니다. 1과 5는 이미 서로 옆에 있으므로 [1,5 ,2] 또는 [4,1,5](또는 그 반대).

이러한 추세를 계속하면서 우리는 배열에 추가할 때 나머지 극단 사이를 앞뒤로 지그재그로 이동하여 n - 1의 최대 k 값을 실제로 달성할 수 있음을 점진적으로 볼 수 있습니다. 이전 예에서 이러한 예 중 하나는 [1,5,2,4,3]입니다.

그런 다음 문제는 1보다 크고 n - 1보다 작은 k의 중간 값을 달성하는 방법에 대해 남아 있습니다. 이에 대한 답은 어레이가 두 부분으로 구성되는 것을 고려하는 데 있습니다. 첫 번째 부분인 [1, k+1]에서 우리는 k개의 절대 차이를 달성할 수 있습니다. 그런 다음 값을 늘리지 않고 이상적인 증분 값으로 나머지 범위인 [k+2, n]을 간단히 채울 수 있습니다. k의.

예를 들어 n = 8이고 k = 4인 경우 마지막 예인 [1,5,2,4,3]과 동일한 첫 번째 부분을 만든 다음 나머지 값을 오름차순으로 추가합니다. , [6,7,8], wole 배열을 만들기 위해 [1,5,2,4,3,6,7,8].

n = 8일 때 k의 각 변형 예:



지그재그 채우기를 달성하기 위해 첫 번째 부분(a, z)의 상단 및 하단 값에 대한 변수를 사용한 다음 모듈로 연산(i % 2)을 사용하여 두 옵션 사이를 번갈아 가며 증가/감소를 기억할 수 있습니다. 각각의 변수가 사용될 때마다.

솔루션의 시각화하기가 약간 더 쉬운(하지만 코딩하기는 더 어려운) 버전은 유사하게 첫 번째 k 요소에 대해 동일한 지그재그를 사용하지만 전체 범위의 n 숫자를 사용한 다음 이상적인 방식으로 이동합니다(증가 또는 감소). 1, k가 짝수인지 홀수인지에 따라) 배열의 나머지 요소를 채웁니다.

n = 8일 때 k의 각 대체 변형의 예:

구현:

네 가지 언어 각각 간에는 약간의 차이만 있습니다.

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )

var constructArray = function(n, k) {
    let ans = new Array(n)
    for (let i = 0, a = 1, z = k + 1; i <= k; i++)
        ans[i] = i % 2 ? z-- : a++
    for (let i = k + 1; i < n;)
        ans[i] = ++i
    return ans
};

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution:
    def constructArray(self, n: int, k: int) -> List[int]:
        ans, a, z = [0] * n, 1, k + 1
        for i in range(k+1):
            if i % 2:
                ans[i] = z
                z -= 1
            else:
                ans[i] = a
                a += 1
        for i in range(k+1,n):
            ans[i] = i + 1
        return ans

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    public int[] constructArray(int n, int k) {
        int[] ans = new int[n];
        for (int i = 0, a = 1, z = k + 1; i <= k; i++)
            ans[i] = i % 2 == 1 ? z-- : a++;
        for (int i = k+1; i < n;)
            ans[i] = ++i;
        return ans;
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> ans(n);
        for (int i = 0, a = 1, z = k + 1; i <= k; i++)
            ans[i] = i % 2 ? z-- : a++;
        for (int i = k+1; i < n; i++)
            ans[i] = i + 1;
        return ans;
    }
};