دمج مصفوفة مرتبة


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون AMDOCS أجهزة آبل بلومبرغ زركش Facebook جولدمان ساكس IBM جونيبر نتوركس لينكد إن: Microsoft Quikr Snapdeal سينوبسيس تأشيرة زوهو
مجموعة فرز مؤشر اثنين

في دمج مشكلة مصفوفة مرتبة قدمنا اثنان فرزها المصفوفات بترتيب متزايد. في الإدخال أولاً ، قدمنا ​​الرقم الذي تمت تهيئته إلى array1 و array2. هذان الرقمان هما N و M. حجم المصفوفة 1 يساوي مجموع N و M. في المصفوفة 1 يتم تهيئة أول رقم n ثم احتواء m التالي على 0. نحن بحاجة إلى إضافة المصفوفة 2 في المصفوفة 1 بحيث يكون النهائي يظل array1 في ترتيب متزايد. دعنا نرى التنسيق أدناه لفهم أفضل.

نمط الإدخال

السطر الأول يحتوي على قيمتين صحيحتين N و M.

يحتوي السطر الثاني على array1 حيث يتم تهيئة الأرقام N الأولى وأرقام M التالية هي 0.

السطر الثالث يحتوي على array2 الذي يحتوي على أرقام M.

تنسيق الإخراج

اطبع المصفوفة الأولى في سطر واحد حيث يتم فصل القيم بفجوة.

القيود

  • 0 <= N ، M <= 100000
  • المصفوفة 1 [i] <= | 1000000000 | حيث 0 <= أنا
  • المصفوفة 2 [i] <= | 1000000000 |
Sample Input:
5 3
2 3 4 4 8 0 0 0
3 5 7
Sample Output:
2 3 3 4 4 5 7 8

شرح لدمج مصفوفتين تم فرزهما

نحن هنا ملزمون بعدم إنشاء أي مساحة إضافية إذا أنشأنا مساحة أخرى مجموعة لتخزين القيمة بالترتيب الفرز ، نحتاج إلى استخدام تعقيد الفضاء الخطي. لذلك ، هناك طريقة واحدة بسيطة لإضافة الثانية فقط في نهاية المصفوفة 1 ثم فرز المصفوفة 1. في هذا ، لا يمكننا إنشاء أي مساحة إضافية وإيجاد الحل في وقت O (N * logN) فقط.

خوارزمية لصفيف دمج الفرز

Step:1 Set j=0
Step:2 For i in range N to N+M-1:
           a) array1[i]=array2[j]
           b) j=j+1
Step:3 Sort the array1
Step:4 Print the array1

تنفيذ مصفوفة الدمج المصنفة

/*C++ Implementation of "Merge Sorted Array".*/ 
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{
    /*input values.*/
    int n,m;
    cin>>n>>m;
    int array1[n+m];
    for(int i=0;i<n+m;i++)
    {
        cin>>array1[i];
    }
    int array2[m];
    for(int i=0;i<m;i++)
    {
        cin>>array2[i];
    }
    /*add array2 at the end of array1.*/
    int j=0;
    for(int i=n;i<n+m;i++)
    {
        array1[i]=array2[j];
        j++;
    }
    sort(array1,array1+n+m);
    /*print array1*/
    for(int i=0;i<n+m;i++)
    {
        cout<<array1[i]<<" ";
    }
    return 0;
}
7 5
1 2 2 5 8 9 17 0 0 0 0 0
2 5 13 19 21
1 2 2 2 5 5 8 9 13 17 19 21

تعقيد الوقت

O (N * log N) لأننا هنا نؤدي فرز الذي يستغرق N * log N وقتًا لفرز الأرقام N. هنا N هو حجم array1. يعتمد ذلك فقط على المصفوفة الأولى لأننا نضيف المصفوفة الثانية إلى المصفوفة الأولى. يكون حجم المصفوفة الأولى دائمًا أكبر من المصفوفة الثانية.

تعقيد الفضاء

يا (1) لأننا لا نستخدم أي مساحة إضافية بدلاً من مجموعة المدخلات الخاصة بنا. نضع كل القيم في المصفوفة 1 التي تم تحديد حجمها بالفعل لنا. لذلك نحن نقوم فقط بالفرز ونحصل على النتيجة دون إنشاء أي مساحة إضافية لدمج مصفوفتين.

مراجع