เขียนโปรแกรมกลับลำดับอาร์เรย์หรือสตริงใน C++

โจทย์

ได้รับอาร์เรย์หรือสตริง ต้องการกลับลำดับองค์ประกอบ (reverse)

ตัวอย่าง

Input (array): {2, 5, 7, 1, 9}
Output: {9, 1, 7, 5, 2}

Input (string): "Hello!"
Output: "!olleH"

อัลกอริทึม

ใช้ Two Pointers Technique:

1. กำหนด pointer `start` ที่ต้น (index 0) และ `end` ที่ท้าย (index n-1)
2. Swap องค์ประกอบที่ `start` และ `end`
3. Increment `start`, Decrement `end`
4. ทำซ้ำจนกว่า `start >= end`

วิธีที่ 1: Iterative Approach (แนะนำ)

#include <iostream>
#include <algorithm>  // สำหรับ std::swap
using namespace std;

void reverseArrayIterative(int arr[], int start, int end) {
    while (start < end) {
        swap(arr[start], arr[end]);  // ใช้ std::swap
        start++;
        end--;
    }
}

void reverseStringIterative(string& str) {
    int start = 0, end = str.length() - 1;
    while (start < end) {
        swap(str[start], str[end]);
        start++;
        end--;
    }
}

int main() {
    // Array
    int arr[] = {6, 9, 1, 4, 0, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Original Array: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    
    reverseArrayIterative(arr, 0, n - 1);
    
    cout << "Reversed Array: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    
    // String
    string str = "Hello!";
    cout << "\nOriginal String: " << str;
    reverseStringIterative(str);
    cout << "\nReversed String: " << str;
    
    return 0;
}

ผลลัพธ์

Original Array: 6 9 1 4 0 5
Reversed Array: 5 0 4 1 9 6

Original String: Hello!
Reversed String: !olleH

วิธีที่ 2: Recursive Approach

void reverseArrayRecursive(int arr[], int start, int end) {
    if (start >= end) return;
    swap(arr[start], arr[end]);
    reverseArrayRecursive(arr, start + 1, end - 1);
}

void reverseStringRecursive(string& str, int start, int end) {
    if (start >= end) return;
    swap(str[start], str[end]);
    reverseStringRecursive(str, start + 1, end - 1);
}

วิธีที่ 3: ใช้ STL (Best Practice)

#include <algorithm>
#include <vector>
#include <string>

// Array / Vector
reverse(arr, arr + n);           // C-style array
reverse(vec.begin(), vec.end()); // std::vector

// String
reverse(str.begin(), str.end()); // std::string

Complexity

• Time: O(N) - swap N/2 ครั้ง
• Space (Iterative): O(1) - in-place
• Space (Recursive): O(N) - recursion stack

สรุป

การ reverse อาร์เรย์/สตริงควรใช้ std::reverse จาก <algorithm> ซึ่ง optimized, tested, และ readable ที่สุด หากต้อง implement เอง ให้ใช้ iterative two-pointers approach เพื่อประสิทธิภาพและความปลอดภัย