โจทย์
ได้รับอาร์เรย์ arr[] ขนาด n (n เป็นเลขคู่) ประกอบด้วย n/2 ตัวเลขคู่ และ n/2 ตัวเลขคี่ ทางเราต้อง จัดเรียงใหม่ให้เลขคู่อยู่ที่ดัชนีคู่ และเลขคี่อยู่ที่ดัชนีคี่
ตัวอย่าง
Input: arr[] = {5, 1, 6, 4, 3, 8}
Output: {6, 1, 5, 4, 3, 8} (หรือลำดับอื่นที่ถูกต้อง เช่น {4, 1, 6, 5, 8, 3})
แนวทางแก้ปัญหา (Two Pointers)
- กำหนด
eIndex = 0(ดัชนีคู่),oIndex = 1(ดัชนีคี่) - ขยับ eIndex ไปจนกว่าจะเจอเลขคี่ที่อยู่ดัชนีคู่
- ขยับ oIndex ไปจนกว่าจะเจอเลขคู่ที่อยู่ดัชนีคี่
- สลับกัน แล้วเพิ่มดัชนีทีละ 2
- ทำซ้ำจนครบ
โปรแกรมตัวอย่าง
#include <iostream>
#include <algorithm>
using namespace std;
void O_EReshuffle(int arr[], int n) {
int oIndex = 1, eIndex = 0;
for (int i = 0; i < n; ) {
while (eIndex < n && arr[eIndex] % 2 == 0) eIndex += 2;
while (oIndex < n && arr[oIndex] % 2 == 1) oIndex += 2;
if (eIndex < n && oIndex < n) swap(arr[eIndex], arr[oIndex]);
else break;
}
}
int main() {
int arr[] = {5, 1, 6, 4, 3, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Array before Reshuffling: ";
for (int i = 0; i < n; i++) cout << arr[i] << "\t";
O_EReshuffle(arr, n);
cout << "\nArray after Reshuffling: ";
for (int i = 0; i < n; i++) cout << arr[i] << "\t";
return 0;
}
ผลลัพธ์
Array before Reshuffling: 5 1 6 4 3 8 Array after Reshuffling: 4 1 6 5 8 3
