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

เราได้รับอาร์เรย์ประเภทจำนวนเต็มที่มีทั้งจำนวนบวกและลบ สมมติว่า arr[] ของขนาดที่กำหนด งานคือการจัดเรียงอาร์เรย์ใหม่ในลักษณะที่จะมีจำนวนบวกที่จะถูกล้อมรอบด้วยตัวเลขเชิงลบ หากมีตัวเลขบวกและลบมากกว่า จะถูกจัดเรียงที่ส่วนท้ายของอาร์เรย์

ให้เราดูสถานการณ์อินพุตเอาต์พุตที่หลากหลายสำหรับสิ่งนี้ -

ป้อนข้อมูล − int arr[] ={-1, -2, -3, 1, 2, 3}

ผลผลิต − Array before Arrangement:-1 -2 -3 1 2 3การจัดเรียงอาร์เรย์ในรายการบวกและลบสลับกับ O(1) ช่องว่างพิเศษคือ:-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 การจัดเรียงใหม่ของอาร์เรย์ในรายการบวกและลบสลับกับ O(1) ช่องว่างเพิ่มเติมคือ:-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 จะเป็นผลลัพธ์สุดท้าย

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• ป้อนอาร์เรย์ขององค์ประกอบประเภทจำนวนเต็มและคำนวณขนาดของอาร์เรย์

• พิมพ์อาร์เรย์ก่อนดำเนินการจัดเรียงใหม่โดยใช้ลูป FOR

• เรียกใช้ฟังก์ชัน Rearrangement(arr, size) โดยส่งอาร์เรย์และขนาดของอาร์เรย์เป็นพารามิเตอร์

• ภายในฟังก์ชัน การจัดเรียงใหม่ (arr, size)

  • ประกาศตัวแปรจำนวนเต็ม 'ptr' และเริ่มต้นด้วย -1

  • เริ่มวนรอบ FOR จาก i ถึง 0 จนถึง i น้อยกว่าขนาด ภายในลูป ตรวจสอบ IF ptr มากกว่า 0 จากนั้นตรวจสอบว่า arr[i] มากกว่า 0 AND arr[ptr] น้อยกว่า 0 OR arr[i] น้อยกว่า 0 AND arr[ptr] มากกว่า 0 จากนั้นเรียกใช้ฟังก์ชัน move_array (arr, size, ptr, i) และตรวจสอบว่า i - ptr มากกว่า 2 จากนั้นตั้งค่า ptr เป็น ptr + 2 ELSE ตั้งค่า ptr เป็น -1

  • ตรวจสอบ IF ptr ถึง -1 จากนั้นตรวจสอบ arr[i] มากกว่า 0 AND !(i &0x01) หรือ (arr[i] น้อยกว่า 0) AND (i &0x01) จากนั้นตั้งค่า ptr เป็น i

• ภายในฟังก์ชัน move_array(int arr[], int size, int ptr, int temp)

  • ประกาศตัวแปรเป็น 'ch' ของอักขระประเภทและตั้งค่าด้วย arr[temp]

  • เริ่มลูป FOR จาก i ถึง temp จนถึง i มากกว่า ptr ภายในลูป ตั้งค่า arr[i] ด้วย arr[i - 1]

  • ตั้งค่า arr[ptr] เป็น ch.

ตัวอย่าง

#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(){
   //input an array
   int arr[] = {-1, -2, -3, 1, 2, 3};
   int size = sizeof(arr) / sizeof(arr[0]);
   //print the original Array
   cout<<"Array before Arrangement: ";
   for (int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   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