ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ವಿಲೀನಗೊಳಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಆಪಲ್ ಬ್ಲೂಮ್ಬರ್ಗ್ ಬೈಟ್ ಡೇನ್ಸ್ ಸಿಸ್ಕೋ ಇಬೇ Expedia ಫೇಸ್ಬುಕ್ ಗೋಲ್ಡ್ಮನ್ ಸ್ಯಾಚ್ಸ್ ಗೂಗಲ್ ಐಬಿಎಂ ಸಂದೇಶ ಸುಳ್ಳು ಮೈಕ್ರೋಸಾಫ್ಟ್ ನೆಟ್ಫ್ಲಿಕ್ಸ್ ಒರಾಕಲ್ ಟೇಬಲ್ ಉಬರ್ ವರೆ ಯಾಹೂ ಯಾಂಡೆಕ್ಸ್
ಅರೇ ಎರಡು ಪಾಯಿಂಟರ್

“ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳನ್ನು ವಿಲೀನಗೊಳಿಸಿ” ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ಎರಡು ನೀಡಲಾಗಿದೆ ಸರಣಿಗಳು ಅವರೋಹಣವಲ್ಲದ ಕ್ರಮದಲ್ಲಿ ವಿಂಗಡಿಸಲಾಗಿದೆ. ಮೊದಲ ರಚನೆಯು ಸಂಪೂರ್ಣವಾಗಿ ಭರ್ತಿಯಾಗಿಲ್ಲ ಮತ್ತು ಎರಡನೇ ರಚನೆಯ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಸರಿಹೊಂದಿಸಲು ಸಾಕಷ್ಟು ಸ್ಥಳಾವಕಾಶವನ್ನು ಹೊಂದಿದೆ. ನಾವು ಎರಡು ಸರಣಿಗಳನ್ನು ವಿಲೀನಗೊಳಿಸಬೇಕು, ಅಂದರೆ ಮೊದಲ ರಚನೆಯು ಎರಡೂ ಸರಣಿಗಳ ಅಂಶಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ವಿಂಗಡಿಸಲಾಗುತ್ತದೆ ಅವರೋಹಣವಲ್ಲದ ಆದೇಶ.

ಉದಾಹರಣೆ

{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. ಅಗತ್ಯ ಫಲಿತಾಂಶವನ್ನು ಮುದ್ರಿಸಿ

ವಿಲೀನ ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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

ವಿಲೀನ ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಕ್ಲಾಗ್‌ಕೆ)ಅಲ್ಲಿ ಕೆ = ಎನ್ + ಎಂ. ಮೊದಲ ರಚನೆಯ N = ಗಾತ್ರ, ಎರಡನೇ ರಚನೆಯ M = ಗಾತ್ರ. ಎಲ್ಲಾ N + M ಅಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸಿದ ನಂತರ ನಾವು ಮೊದಲ ಶ್ರೇಣಿಯನ್ನು ವಿಂಗಡಿಸುತ್ತೇವೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1) ಸ್ಥಿರ ಮೆಮೊರಿಯನ್ನು ಅಸ್ಥಿರಗಳಿಗಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ.

ಅಪ್ರೋಚ್ (ಎರಡು ಪಾಯಿಂಟರ್ಸ್)

ನಾವು ಬಳಸಬಹುದು ಎರಡು-ಪಾಯಿಂಟರ್ ಎರಡು ವಿಂಗಡಿಸಲಾದ ಸರಣಿಗಳನ್ನು ಹೊಸ ಶ್ರೇಣಿಯಲ್ಲಿ ವಿಲೀನಗೊಳಿಸುವ ತಂತ್ರ. ಆದರೆ, ಈ ಹೊಸ ರಚನೆಯ ರಚನೆಗೆ ಹೆಚ್ಚುವರಿ ಸ್ಥಳಾವಕಾಶ ಬೇಕಾಗುತ್ತದೆ. ಈ ಹೆಚ್ಚುವರಿ ಶ್ರೇಣಿಯನ್ನು ತಪ್ಪಿಸಲು ನಾವು ಪ್ರಯತ್ನಿಸಬಹುದು, ವಿಶೇಷವಾಗಿ ಮೊದಲ ಶ್ರೇಣಿಯು ಎರಡೂ ಸರಣಿಗಳ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಹಿಡಿದಿಡಲು ಸಾಕಷ್ಟು ಸ್ಥಳವನ್ನು ಹೊಂದಿರುವಾಗ. ನಾವು ಎರಡು ಪಾಯಿಂಟರ್‌ಗಳನ್ನು ಬಳಸಬಹುದು ಮತ್ತು ಮೊದಲ ರಚನೆಯ ಹಿಂಭಾಗದಲ್ಲಿರುವ ಅಂಶಗಳನ್ನು ವಿಲೀನಗೊಳಿಸಲು ಪ್ರಾರಂಭಿಸಬಹುದು.

ಅನೂರ್ಜಿತ ಜಾಗದಲ್ಲಿ ನಾವು ಅಂಶಗಳನ್ನು ಸರಿಪಡಿಸುತ್ತಿರುವುದರಿಂದ ಇದು “ಹೆಚ್ಚುವರಿ ಅರೇ ಮೆಮೊರಿ” ಯ ಸಮಸ್ಯೆಯನ್ನು ಕಡಿತಗೊಳಿಸುತ್ತದೆ.

ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ವಿಲೀನಗೊಳಿಸಿ

ಕ್ರಮಾವಳಿ

  1. ಎರಡು ಅಸ್ಥಿರಗಳನ್ನು ಪ್ರಾರಂಭಿಸಿ i ಮತ್ತು j ಮೊದಲ ಮತ್ತು ಎರಡನೆಯ ರಚನೆಯ ಕೊನೆಯ ಅಂಶದ ಸೂಚ್ಯಂಕಗಳನ್ನು ಕ್ರಮವಾಗಿ ಸಂಗ್ರಹಿಸುವುದು.
    • i = M - 1, j = N - 1
  2. ವೇರಿಯಬಲ್ ಅನ್ನು ಪ್ರಾರಂಭಿಸಿ idx, ಮೊದಲ ರಚನೆಯ ಕೊನೆಯ ಸೂಚಿಯನ್ನು ಸಂಗ್ರಹಿಸುವುದು, ಅಂದರೆ:
    • idx = N + M - 1
  3. ಈಗ, ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಮಾಡಿ i or j ಶೂನ್ಯವಾಗುತ್ತದೆ
    • ಒಂದು [i]> = ಬಿ [ಜೆ] ಆಗಿದ್ದರೆ
      • [Idx] = a [i], ಇಳಿಕೆ ನಿಗದಿಪಡಿಸಿ i
    • ಬೇರೆ
      • [Idx] = b [j], ಇಳಿಕೆ ನಿಗದಿಪಡಿಸಿ j
    • ಇಳಿಕೆ idx
  4. ಒಂದೋ i ಅಥವಾ ಜೆ ಶೂನ್ಯವಲ್ಲ, ಇದರರ್ಥ ಕೆಲವು ಅಂಶಗಳನ್ನು ಇನ್ನೂ ವಿಲೀನಗೊಳಿಸಬೇಕಾಗಿಲ್ಲ. ಅವರು ಈಗಾಗಲೇ ವಿಂಗಡಿಸಲಾದ ರೀತಿಯಲ್ಲಿ ಇರುವುದರಿಂದ, ನಾವು ಅವುಗಳನ್ನು ಮುಂಭಾಗದ ಮೊದಲ ಶ್ರೇಣಿಗೆ ಸೇರಿಸುತ್ತೇವೆ.
  5. ಆದರೆ i ಶೂನ್ಯವಾಗುವುದಿಲ್ಲ,
    1. [Idx] = a [i] ಅನ್ನು ನಿಯೋಜಿಸಿ
    2. ಇಳಿಕೆ idx ಮತ್ತು i
  6. ಆದರೆ j ಶೂನ್ಯವಾಗುವುದಿಲ್ಲ,
    1. [Idx] = b [j] ಅನ್ನು ನಿಯೋಜಿಸಿ
    2. ಇಳಿಕೆ idx ಮತ್ತು j
  7. ಈಗ ಮೊದಲ ಶ್ರೇಣಿಯು ಅಗತ್ಯವಿರುವ ವಿಂಗಡಿಸಲಾದ ಕ್ರಮದಲ್ಲಿ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಹೊಂದಿದೆ.

ವಿಲೀನ ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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

ವಿಲೀನ ವಿಂಗಡಿಸಲಾದ ಅರೇಗಳ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ + ಎಂ). N = ಮೊದಲ ರಚನೆಯ ಗಾತ್ರ, M = ಎರಡನೇ ರಚನೆಯ ಗಾತ್ರ. ನಾವು ಎರಡೂ ಸರಣಿಗಳನ್ನು ಒಮ್ಮೆ ಹಾದುಹೋಗುವಾಗ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1), ನಾವು ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಮೊದಲ ಶ್ರೇಣಿಯಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ. ಆದ್ದರಿಂದ, ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ ಸ್ಥಳದಲ್ಲಿ.