667. Beautiful Arrangement II

leetcode medium

#array#csharp#leetcode#medium#two-pointers

Task

Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию:

Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них.

Пример

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

C# solution

matched/original

public class Solution {
    public int[] ConstructArray(int n, int k) {
        int[] answer = new int[n];
        int left = 1, right = n;
        
        for (int i = 0; i <= k; i++) {
            if (i % 2 == 0) {
                answer[i] = left++;
            } else {
                answer[i] = right--;
            }
        }
        
        if (k % 2 == 0) {
            for (int i = k + 1; i < n; i++) {
                answer[i] = right--;
            }
        } else {
            for (int i = k + 1; i < n; i++) {
                answer[i] = left++;
            }
        }
        
        return answer;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& ConstructArray(int n, int k) {
        vector<int>& answer = new int[n];
        int left = 1, right = n;
        
        for (int i = 0; i <= k; i++) {
            if (i % 2 == 0) {
                answer[i] = left++;
            } else {
                answer[i] = right--;
            }
        }
        
        if (k % 2 == 0) {
            for (int i = k + 1; i < n; i++) {
                answer[i] = right--;
            }
        } else {
            for (int i = k + 1; i < n; i++) {
                answer[i] = left++;
            }
        }
        
        return answer;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int[] ConstructArray(int n, int k) {
        int[] answer = new int[n];
        int left = 1, right = n;
        
        for (int i = 0; i <= k; i++) {
            if (i % 2 == 0) {
                answer[i] = left++;
            } else {
                answer[i] = right--;
            }
        }
        
        if (k % 2 == 0) {
            for (int i = k + 1; i < n; i++) {
                answer[i] = right--;
            }
        } else {
            for (int i = k + 1; i < n; i++) {
                answer[i] = left++;
            }
        }
        
        return answer;
    }
}

Python solution

matched/original

def constructArray(n, k):
    answer = []
    left, right = 1, n
    
    for i in range(k + 1):
        if i % 2 == 0:
            answer.append(left)
            left += 1
        else:
            answer.append(right)
            right -= 1
    
    if k % 2 == 0:
        answer.extend(range(left, right + 1))
    else:
        answer.extend(range(right, left - 1, -1))
    
    return answer

Explanation

Algorithm

1⃣Инициализация списка:

Начните с создания списка от 1 до n: [1, 2, 3, ..., n].

2⃣Конструирование шаблона с k различиями:

Для обеспечения k различных значений разностей используйте следующий подход:

Включайте числа попеременно с конца и начала списка, начиная с n и 1, чтобы создать как можно больше уникальных разностей.

Если требуется меньше k, оставшиеся числа просто добавляйте в порядке возрастания, чтобы не увеличивать количество уникальных разностей.

3⃣Заполнение списка:

Заполните оставшуюся часть списка последовательными числами, чтобы сохранить уникальные числа в диапазоне от 1 до n.

😎