จัดเรียงจำนวนบวกและลบสลับกัน O(n) เวลา O(1) พื้นที่ใน C++

ภาพรวม

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

ตัวอย่าง

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

เอาต์พุต − Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -1 6 -1 4 -3

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

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

เอาต์พุต − Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -2 3 -5 5 -3 5 -1 1 3 1 1

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

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

• รับอาร์เรย์ คำนวณขนาด
• พิมพ์อาร์เรย์ก่อนจัดเรียง
• เรียก Rearrangement(arr, size)
• ภายในฟังก์ชัน:
  • temp = -1
  • วน i=0 ถึง size-1: หาก arr[i] < 0 temp++ สลับ arr[temp] กับ arr[i] (ย้ายลบทั้งหมดไปซ้าย)
  • positive = temp + 1 (ดัชนีแรกของบวก) negative = 0
  • while positive < size && negative < positive && arr[negative] < 0:
    • สลับ arr[negative] กับ arr[positive]
    • positive++ negative += 2
• พิมพ์ผลลัพธ์

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

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

void Rearrangement(int arr[], int size){ 
    int temp = -1; 
    for(int i = 0; i < size; i++){ 
        if (arr[i] < 0){ 
            temp++; 
            swap(arr[temp], arr[i]); 
        } 
    } 
    int positive = temp + 1; 
    int negative = 0; 
    while(positive < size && negative < positive && arr[negative] < 0){ 
        swap(arr[negative], arr[positive]); 
        positive++; 
        negative = negative + 2; 
    } 
} 

int main(){ 
    int arr[] = {4, 2, -1, -1, 6, -3}; 
    int size = sizeof(arr)/sizeof(arr[0]); 
    Rearrangement(arr, size); 
    cout << "Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: "; 
    for(int i = 0; i < size; i++){ 
        cout << arr[i] << " "; 
    } 
    return 0; 
}

ผลลัพธ์

Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -1 6 -1 4 -3