צונויפגיסן סאָרטעד ערייז לעעטקאָדע סאַלושאַן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַדאָובי אַמאַזאָן עפּל בלומבערג ביטעדאַנסע סיסקאָ עבייַ עקספּעדיאַ facebook גאָלדמאַן סאַקס גוגל יבם לינקעדין lyft מייקראָסאָפֿט Netflix אָראַקל טיש ובער וומוואַרע יאַהאָאָ יאַנדעקס
מענגע צוויי טייַטל

אין דעם פּראָבלעם "צונויפגיסן סאָרטעד ערייז", מיר זענען צוויי ערייז אויסגעשטעלט אין נישט אראפנידערן סדר. דער ערשטער מענגע איז נישט פול אָנגעפילט און האט גענוג פּלאַץ צו אַקאַמאַדייט אַלע יסודות פון די רגע מענגע. מיר מוזן צונויפגיסן די צוויי ערייז אַזוי אַז דער ערשטער מענגע כּולל עלעמענטן פון ביידע ערייז און איז אויסגעשטעלט נישט אראפנידערן סדר.

בייַשפּיל

{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. אַ [i + m] = b [i], אַ = ערשטער מענגע, b = רגע מענגע
  2. סאָרט די ערשטער מענגע
  3. דרוק דעם פארלאנגט רעזולטאַט

ימפּלעמענטאַטיאָן פון צונויפגיסן סאָרטעד ערייז לעעטקאָדע סאַלושאַן

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;
}

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פון צונויפגיסן סאָרטעד ערייז לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (קלאָגק), ווו ק = ען + ב. N = גרייס פון דער ערשטער מענגע, M = גרייס פון די רגע מענגע. מיר סאָרטירן די ערשטער מענגע נאָך סטאָרד אַלע N + M עלעמענטן.

ספעיס קאַמפּלעקסיטי

אָ (1) ווי קעסיידערדיק זיקאָרן איז געניצט פֿאַר וועריאַבאַלז.

צוגאַנג (צוויי פּוינטערז)

מיר קענען נוצן צוויי-טייַטל טעכניק צו צונויפגיסן די צוויי סאָרטעד ערייז, אין אַ נייַע מענגע. די שאַפונג פון דעם נייַע מענגע וועט קאָסטן עקסטרע פּלאַץ. מיר קענען פּרובירן צו ויסמיידן דעם עקסטרע מענגע, ספּעציעל ווען דער ערשטער מענגע האט גענוג פּלאַץ צו האַלטן אַלע די יסודות פון ביידע ערייז. מיר קענען נוצן צוויי פּוינטערז און אָנהייבן צונויפגיסן די עלעמענטן אין דער צוריק פון דער ערשטער מענגע.

דאָס וועט שנייַדן די פּראָבלעם פון "עקסטרע מענגע זכּרון" ווען מיר האַלטן פיקסיר די עלעמענטן אין די פּאָסל פּלאַץ.

צונויפגיסן סאָרטעד ערייז לעעטקאָדע סאַלושאַן

אַלגאָריטהם

  1. יניטיאַליזירן צוויי וועריאַבאַלז i און j סטאָרינג ינדאַסיז פון די לעצטע עלעמענט פון דער ערשטער און רגע מענגע ריספּעקטיוולי.
    • i = M - 1, j = N - 1
  2. יניטיאַליזירן אַ בייַטעוודיק ידקס, סטאָרינג די לעצטע אינדעקס פון דער ערשטער מענגע, דאָס איז:
    • ידקס = N + M - 1
  3. איצט טאָן די פאלגענדע ביז איינער פון די i or j ווערט נול
    • אויב אַ [i]> = b [j]
      • באַשטימען אַ [ידקס] = אַ [איך], דעקרעד i
    • אַנדערש
      • באַשטימען אַ [ידקס] = b [j], דעקרעד j
    • דעקרעד ידקס
  4. אָדער פון איך אָדער דזש איז ניט נול, וואָס מיטל עטלעכע עלעמענטן זענען נאָך צו זיין מערדזשד. ווי זיי וואָלט שוין זיין אין אַ סאָרטעד שטייגער, מיר פשוט צולייגן זיי צו דער ערשטער מענגע אין די פראָנט.
  5. ווייַלע i ווערט נישט נול,
    1. באַשטימען אַ [ידקס] = אַ [איך]
    2. דעקרעד ידקס און i
  6. ווייַלע j ווערט נישט נול,
    1. באַשטימען אַ [ידקס] = b [j]
    2. דעקרעד ידקס און j
  7. דער ערשטער מענגע האט אַלע די עלעמענטן אין די פארלאנגט סדר.

ימפּלעמענטאַטיאָן פון צונויפגיסן סאָרטעד ערייז לעעטקאָדע סאַלושאַן

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;
}

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פון צונויפגיסן סאָרטעד ערייז לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (N + M). N = גרייס פון דער ערשטער מענגע, M = גרייס פון די רגע מענגע. ווען מיר פאָרן ביידע די ערייז אַמאָל.

ספעיס קאַמפּלעקסיטי

אָ (1), ווי מיר קראָם אַלע די עלעמענטן אין דער ערשטער מענגע. אַזוי, דער אַלגערידאַם איז אין פּלאַץ.