สร้างอาร์เรย์ Beautiful Arrangement II ใน C++

ให้จำนวนเต็ม n และ k ต้องสร้างลิสต์ที่มี n จำนวนเต็มบวกต่างกันจาก 1 ถึง n โดยที่ลิสต์ของความต่างสัมบูรณ์ระหว่างสมาชิกติดกันมีค่าที่ไม่ซ้ำกัน k ค่า

ตัวอย่าง: n = 3, k = 2 → ผลลัพธ์ [1,3,2] ความต่างคือ [2,1] มีค่าที่ไม่ซ้ำกัน 2 ค่า คือ 1 และ 2

วิธีแก้ปัญหา (Two Pointers)

1. สร้างอาร์เรย์ ret ว่าง
2. ใช้ตัวชี้ i = 1, j = n
3. วนลูป while i ≤ j:
   • ถ้า k > 1:
     • ถ้า k เป็นเลขคี่ → ใส่ i ลง ret, เพิ่ม i
     • ถ้า k เป็นเลขคู่ → ใส่ j ลง ret, ลด j
     • ลด k ลง 1
   • มิฉะนั้น ใส่ i ลง ret และเพิ่ม i
4. คืนค่า ret

ตัวอย่างโค้ด C++

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

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> ret;
        for (int i = 1, j = n; i <= j; ) {
            if (k > 1) {
                ret.push_back(k % 2 ? i : j);
                if (k % 2 == 1) i++;
                else j--;
                k--;
            } else {
                ret.push_back(i++);
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    print_vector(ob.constructArray(3, 2));
    return 0;
}

Input

3 2

Output

[3, 1, 2, ]