จัดเรียงตัวเลขบวกและลบใหม่ในเวลา O(n) และช่องว่างพิเศษ O(1) ใน C++

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

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

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

ผลผลิต − การจัดเรียงตัวเลขบวกและลบในเวลา O(n) และช่องว่างพิเศษ O(1) คือ: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}

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

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

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

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

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

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

  • ประกาศตัวแปรประเภทจำนวนเต็มชั่วคราว เช่น temp เป็น -1, positive to temp + 1 และลบเป็น 0.

  • เริ่มวนรอบ FOR จาก i ถึง 0 จนถึง i น้อยกว่าขนาดของอาร์เรย์ ภายในลูป ให้ตรวจสอบว่า arr[i] น้อยกว่า 0 แล้วเพิ่ม temp ขึ้น 1 และเรียกวิธีการ inbuilt ของ C++ STL เช่น swap(arr[temp], arr[i]) และส่งผ่าน arr[temp] และ arr[i ] เป็นพารามิเตอร์

  • เริ่มวนรอบ ขณะที่ค่าบวกน้อยกว่าขนาดของอาร์เรย์ และค่าลบน้อยกว่าค่าบวก AND arr[เชิงลบ] ที่น้อยกว่า 0 ภายในลูป ให้สลับการโทรโดยส่ง arr[เชิงลบ] และ arr[บวก] เป็นพารามิเตอร์ เพิ่มค่าบวก 1 และตั้งค่าลบเป็นลบ + 2

• พิมพ์ผลลัพธ์

ตัวอย่าง

#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]);
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   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