دمج حل Leetcode المصفوفات المصنفة  


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل بلومبرغ ByteDance سيسكو يباي اكسبيديا Facebook جولدمان ساكس جوجل IBM لينكد إن: lyft Microsoft نيتفليكس أوراكل التابلوه لوحة حية اوبر في إم وير ياهو ياندكس
خوارزميات مجموعة الترميز المقابلة الشخصية مقابلة LeetCode LeetCodeSolutions مؤشر اثنين

في مشكلة "دمج المصفوفات المصنفة" ، حصلنا على اثنين المصفوفات مرتبة بترتيب غير تنازلي. المصفوفة الأولى ليست ممتلئة بالكامل ولديها مساحة كافية لاستيعاب جميع عناصر المصفوفة الثانية أيضًا. علينا دمج المصفوفتين ، بحيث تحتوي المصفوفة الأولى على عناصر من كلا المصفوفتين ويتم فرزها في غير تنازلي النظام.

مثال  

{1 , 2 , 3 , - , - , -}
{2 , 6 , 7}
1 2 2 3 6 7
{1 , 1 , 1 ,  - , -}
{2 , 4}
1 1 1 2 4

النهج (الفرز)  

يمكننا نقل جميع عناصر المصفوفة الثانية إلى الأولى. يمكننا بعد ذلك فرز المصفوفة الأولى للحصول على النتيجة المطلوبة.

خوارزمية

  1. من أجل i = 0 إلى i = N ، قم بتعيين
    1. a [i + m] = b [i] ، a = المصفوفة الأولى ، b = المصفوفة الثانية
  2. فرز المصفوفة الأولى
  3. اطبع النتيجة المطلوبة

تنفيذ حل Leetcode للصفائف المصنفة بالدمج

برنامج C ++

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

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    for(int i = 0 ; i < n ; i++)
        a[i + m] = b[i];

    sort(a.begin() , a.end());
    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

برنامج جافا

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        for(int i = 0 ; i < n ; i++)
            a[i + m] = b[i];
        Arrays.sort(a);
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}
1 2 2 3 6 7

تحليل التعقيد لحل Leetcode للصفائف المصنفة بالدمج

تعقيد الوقت

يا (كلوغك)، حيث ك = N + م. N = حجم المصفوفة الأولى ، M = حجم المصفوفة الثانية. كما نقوم بفرز المصفوفة الأولى بعد أن تقوم بتخزين جميع عناصر N + M.

انظر أيضا
زيادة تناقص سلسلة Leetcode الحل

تعقيد الفضاء

يا (1) كذاكرة ثابتة تستخدم للمتغيرات.

النهج (مؤشرين)  

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

سيؤدي هذا إلى التخلص من مشكلة "ذاكرة المصفوفة الإضافية" بينما نستمر في إصلاح العناصر في مساحة الفراغ.

دمج حل Leetcode المصفوفات المصنفة

خوارزمية

  1. تهيئة متغيرين i و j تخزين مؤشرات العنصر الأخير في الصفيف الأول والثاني على التوالي.
    • أنا = م - 1 ، ي = ن - 1
  2. تهيئة متغير IDX، تخزين الفهرس الأخير للمصفوفة الأولى ، وهو:
    • المعرّف = N + M - 1
  3. الآن ، قم بما يلي حتى أي من i or j يصبح صفر
    • إذا كان [i]> = b [j]
      • قم بتعيين [idx] = a [i] ، التناقص i
    • آخر
      • قم بتعيين a [idx] = b [j] ، التناقص j
    • النقص IDX
  4. أيا من أنا أو ي ليست صفراً ، مما يعني أن بعض العناصر لم يتم دمجها بعد. نظرًا لأنهم سيكونون بالفعل بطريقة مرتبة ، فإننا ببساطة نلحقهم بالمصفوفة الأولى في المقدمة.
  5. ليس i لا تصبح صفرا ،
    1. تعيين [idx] = a [i]
    2. النقص IDX و i
  6. ليس j لا تصبح صفرا ،
    1. تعيين [idx] = b [j]
    2. النقص IDX و j
  7. الآن تحتوي المصفوفة الأولى على جميع العناصر بالترتيب الفرز المطلوب.

تنفيذ حل Leetcode للصفائف المصنفة بالدمج

برنامج C ++

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

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    int i = m - 1 , j = n - 1 , idx = m + n - 1;
    while(i >= 0 && j >= 0)
    {
        if(a[i] >= b[j])
        {
            a[idx] = a[i];
            i--;
        }
        else
        {
            a[idx] = b[j];
            j--;
        }
        idx--;
    }


    while(i >= 0)
        a[idx--] = a[i--];

    while(j >= 0)
        a[idx--] = b[j--];

    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

برنامج جافا

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        int i = m - 1 , j = n - 1 , idx = m + n - 1;
        while(i >= 0 && j >= 0)
        {
            if(a[i] >= b[j])
            {
                a[idx] = a[i];
                i--;
            }
            else
            {
                a[idx] = b[j];
                j--;
            }
            idx--;
        }

        while(i >= 0)
            a[idx--] = a[i--];

        while(j >= 0)
            a[idx--] = b[j--];

        return;
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}
1 2 2 3 6 7

تحليل التعقيد لحل Leetcode للصفائف المصنفة بالدمج

تعقيد الوقت

يا (N + M). N = حجم المصفوفة الأولى ، M = حجم المصفوفة الثانية. بينما نجتاز كلا المصفوفتين مرة واحدة.

انظر أيضا
قوة أربعة حل Leetcode

تعقيد الفضاء

يا (1) ، حيث نقوم بتخزين جميع العناصر في المصفوفة الأولى. إذن ، الخوارزمية في المكان.