องค์ประกอบบวกอยู่ตำแหน่งคู่ และลบอยู่ตำแหน่งคี่ (Relative order not maintained) ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์และงานของเราคือแปลงอาร์เรย์ในลักษณะที่ตัวเลขบวกทั้งหมดอยู่ที่ตำแหน่งดัชนีคู่ และตัวเลขลบทั้งหมดอยู่ที่ตำแหน่งดัชนีคี่

อาจมีจำนวนค่าบวกและค่าลบไม่เท่ากัน ในกรณีนี้ เราจะไม่ย้ายค่าที่เหลือ

มาดูตัวอย่างเพื่อเข้าใจปัญหา:

Input - {3, 5, -1, 19, -7, -2}

Output - {3, -1, 5, -7, 19, -2}

เพื่อแก้ปัญหานี้ เราจะต้องหาองค์ประกอบที่อยู่นอกลำดับในอาร์เรย์ อาจมีมากกว่าหนึ่งวิธีในการหาสิ่งนี้ ที่นี่เราจะอภิปรายสองวิธีของพวกเขา

วิธีที่ 1

วิธีนี้จะแค่ท่องอาร์เรย์และหาการเกิดครั้งแรกขององค์ประกอบที่ไม่อยู่ในตำแหน่ง (เช่น บวกไม่อยู่ที่ดัชนีคู่ และลบไม่อยู่ที่ดัชนีคี่) แล้วสลับพวกมัน เราจะทำกระบวนการนี้จนกว่าจะท่องอาร์เรย์ทั้งหมด

ตัวอย่าง

โปรแกรมแสดงการนำโซลูชันของเราไปใช้งาน:

#include <iostream>
using namespace std;

void swapElements(int* a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    return;
}

void printArray(int* a, int n) {
    for(int i = 0; i < n; i++)
        cout << a[i] << "\t";
    cout << endl;
    return;
}

void generateOrderedArray(int arr[], int n) {
    for(int i = 0; i < n; i++) {
        if(arr[i] >= 0 && i % 2 == 1) {
            for(int j = i + 1; j < n; j++) {
                if(arr[j] < 0 && j % 2 == 0) {
                    swapElements(arr, i, j);
                    break;
                }
            }
        } else if(arr[i] < 0 && i % 2 == 0) {
            for(int j = i + 1; j < n; j++) {
                if(arr[j] >= 0 && j % 2 == 1) {
                    swapElements(arr, i, j);
                    break;
                }
            }
        }
    }
    printArray(arr, n);
}

int main() {
    int arr[] = { 1, -3, 5, 6, -3, 6, 7, -4, 9, 10 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Inital Array is : ";
    printArray(arr, n);
    cout << "Array with positive numbers at even index and negative numbers at odd index :";
    generateOrderedArray(arr,n);
    return 0;
}

ผลลัพธ์

Inital Array is : 3 5 -1 19 -7 -2
Array with positive numbers at even index and negative numbers at odd index : 3 -1 5 -7 19 -2

วิธีที่ 2

ในวิธีนี้ เราจะใช้กระบวนการที่จะดูเหมือน quick sort technique ที่นี่ เราจะใช้สองตัวชี้ (pointers) หนึ่งสำหรับตัวเลขบวกและอีกอันสำหรับตัวเลขลบ เราจะตั้งค่า positive pointer ที่ดัชนี 0 (ดัชนีคู่) และ negative ที่ดัชนี 1 (ดัชนีคี่) และก้าวไปข้างหน้าทีละ 2 และหยุดเมื่อ positive pointer พบตัวเลขลบและ negative pointer พบตัวเลขบวก แล้วสลับเมื่อทั้งสองหยุด หากตัวชี้ใดตัวชี้หนึ่งออกนอกดัชนีอาร์เรย์ เราจะหยุดการทำงาน

ตัวอย่าง

โปรแกรมแสดงการนำโซลูชันของเราไปใช้งาน:

#include <iostream>
using namespace std;

void swapElements(int* a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    return;
}

void printArray(int *a, int n) {
    for (int i = 0; i < n; i++)
        cout << a[i] << "\t";
    cout << endl;
}

void generateOrderedArray(int a[], int size) {
    int positive = 0, negative = 1;
    while (1) {
        while (positive < size && a[positive] >= 0)
            positive += 2;
        while (negative < size && a[negative] <= 0)
            negative += 2;
        if (positive < size && negative < size)
            swapElements(a, positive, negative);
        else
            break;
    }
}

int main() {
    int arr[] = { 3, 5, -1, 19, -7, -2 };
    int n = (sizeof(arr) / sizeof(arr[0]));
    cout << "Inital Array is : ";
    printArray(arr, n);
    cout << "Array with positive numbers at even index and negative numbers at odd index : ";
    generateOrderedArray(arr, n);
    printArray(arr, n);
    return 0;
}

ผลลัพธ์

Inital Array is : 3 5 -1 19 -7 -2
Array with positive numbers at even index and negative numbers at odd index : 3 -1 5 -7 19 -2