จัดเรียงอาร์เรย์ให้บวกและลบสลับกัน O(1) พื้นที่เพิ่มเติมใน C++

ภาพรวม

ได้รับอาร์เรย์จำนวนเต็ม arr[] มีทั้งบวกและลบ งานคือจัดเรียงใหม่ให้มีรูปแบบ: บวกอยู่กลางลบ (Positive surrounded by negatives) หากฝั่งใดมากกว่า ให้วางส่วนเกินท้ายอาร์เรย์

ตัวอย่าง

อินพุต − int arr[] = {-1, -2, -3, 1, 2, 3}

เอาต์พุต − Array before Arrangement: -1 -2 -3 1 2 3

Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3

คำอธิบาย − อาร์เรย์ขนาด 6 จัดเรียงให้บวกลบสลับกัน ลบ-บวก-ลบ-บวก... ได้ -1 1 -2 2 -3 3

อินพุต − int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}

เอาต์พุต − Array before Arrangement: -1 -2 -3 1 2 3 5 5 -5 3 1 1

Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3 -5 5 5 3 1 1

คำอธิบาย − อาร์เรย์ขนาด 12 จัดเรียงบวกลบสลับกัน ส่วนเกินวางท้าย ได้ -1 1 -2 2 -3 3 -5 5 5 3 1 1

แนวทางการแก้ปัญหา

• รับอาร์เรย์ คำนวณขนาด
• พิมพ์อาร์เรย์ก่อนจัดเรียง
• เรียก Rearrangement(arr, size)
• ภายในฟังก์ชัน:
  • ptr = -1
  • วน i=0 ถึง size-1:
    • หาก ptr >= 0 และ (arr[i] >= 0 && arr[ptr] < 0 หรือ arr[i] < 0 && arr[ptr] >= 0):
      • เรียก move_array(arr, size, ptr, i) ย้ายอิลิเมนต์
      • หาก i - ptr >= 2 ptr += 2 มิฉะนั้น ptr = -1
    • หาก ptr == -1 และ (arr[i] >= 0 && !(i & 0x01) หรือ arr[i] < 0 && (i & 0x01)) ตั้ง ptr = i
  • ฟังก์ชัน move_array(arr, size, ptr, temp):
    • ch = arr[temp]
    • วน i = temp; i > ptr; i-- arr[i] = arr[i-1]
    • arr[ptr] = ch
• พิมพ์ผลลัพธ์

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

#include <iostream> 
#include <assert.h> 
using namespace std; 

void move_array(int arr[], int size, int ptr, int temp){ 
    char ch = arr[temp]; 
    for(int i = temp; i > ptr; i--){ 
        arr[i] = arr[i - 1]; 
    } 
    arr[ptr] = ch; 
} 

void Rearrangement(int arr[], int size){ 
    int ptr = -1; 
    for(int i = 0; i < size; i++){ 
        if (ptr >= 0){ 
            if(((arr[i] >= 0) && (arr[ptr] < 0)) || ((arr[i] < 0) && (arr[ptr] >= 0))){ 
                move_array(arr, size, ptr, i); 
                if(i - ptr >= 2){ 
                    ptr = ptr + 2; 
                } else { 
                    ptr = -1; 
                } 
            } 
        } 
        if(ptr == -1){ 
            if (((arr[i] >= 0) && (!(i & 0x01))) || ((arr[i] < 0) && (i & 0x01))){ 
                ptr = i; 
            } 
        } 
    } 
} 

int main(){ 
    int arr[] = {-1, -2, -3, 1, 2, 3}; 
    int size = sizeof(arr) / sizeof(arr[0]); 
    cout << "Array before Arrangement: "; 
    for (int i = 0; i < size; i++){ 
        cout << arr[i] << " "; 
    } 
    Rearrangement(arr, size); 
    cout << "\nRearrangement of an array in alternating positive & negative items with O(1) extra space is: "; 
    for(int i = 0; i < size; i++){ 
        cout << arr[i] << " "; 
    } 
    return 0; 
}

ผลลัพธ์

Array before Arrangement: -1 -2 -3 1 2 3 
Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3