የተደረደሩ ድርድሮች Leetcode መፍትሄን ያዋህዱ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን ፓም ብሉምበርግ ByteDance Cisco eBay Expedia ፌስቡክ ጎልድማን ሳክስ google IBM LinkedIn ግራፍ የ Microsoft Netflix በ Oracle Tableau በ Uber VMware ያሁ Yandex
ሰልፍ ሁለት ጠቋሚ

በተፈጠረው ችግር “የተደረደሩ ድርድሮች” ውስጥ ሁለት ተሰጠን ድርድሮች ባልወረደ ቅደም ተከተል ተደርድሯል። የመጀመሪያው ድርድር ሙሉ በሙሉ አልተሞላም እና የሁለተኛውን ድርድር ሁሉንም አካላት እንዲሁ ለማስተናገድ የሚያስችል በቂ ቦታ አለው። ሁለቱን ድርድሮች ማዋሃድ አለብን ፣ የመጀመሪያው ረድፍ የሁለቱም ድርድር አካላት የያዘ እና የተስተካከለ ነው የማይወርድ ትእዛዝ.

ለምሳሌ

{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 = የመጀመሪያ ድርድር ፣ ለ = ሁለተኛ ድርድር
  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 መፍትሔ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ክሎክ)የት K = N + M. N = የመጀመሪያው ድርድር መጠን ፣ M = የሁለተኛው ድርድር። ሁሉንም የ N + M አካላት ካከማቸ በኋላ የመጀመሪያውን ድርድር እንደደረደርነው።

የቦታ ውስብስብነት

ኦ (1) እንደ ተለዋዋጭ ማህደረ ትውስታ ለተለዋጮች ጥቅም ላይ ይውላል ፡፡

አቀራረብ (ሁለት ጠቋሚዎች)

መጠቀም እንችላለን ባለ ሁለት ጠቋሚ ሁለቱን የተደረደሩ ድርድሮች ወደ አዲስ ድርድር ለማዋሃድ የሚያስችል ዘዴ ፡፡ ግን ፣ የዚህ አዲስ ድርድር መፈጠር ተጨማሪ ቦታ ያስከፍላል። በተለይም የመጀመሪያው ድርድር የሁለቱም የዝግጅት ክፍሎች ሁሉንም ነገሮች ለመያዝ የሚያስችል በቂ ቦታ ሲኖር ይህንን ተጨማሪ ድርድር ለማስወገድ መሞከር እንችላለን። ሁለት ጠቋሚዎችን መጠቀም እና ከመጀመሪያው ድርድር ጀርባ ያሉትን ንጥረ ነገሮች ማዋሃድ መጀመር እንችላለን ፡፡

ባዶ ቦታ ላይ ያሉትን ንጥረ ነገሮች መጠገን ስንቀጥል ይህ “ተጨማሪ የድርጅት ማህደረ ትውስታ” ችግርን ይቆርጠዋል።

የተደረደሩ ድርድሮች Leetcode መፍትሄን ያዋህዱ

አልጎሪዝም

  1. ሁለት ተለዋዋጮችን ያስጀምሩ ij የአንደኛውን እና የሁለተኛው ድርድርን የመጨረሻ ክፍል ማውጫዎች በቅደም ተከተል ማከማቸት።
    • i = M - 1, j = N - 1
  2. ተለዋዋጭን ያስጀምሩ መታወቂያየመጀመሪያውን ድርድር የመጨረሻ ማውጫ ማከማቸት ፣ ያ
    • idx = N + M - 1
  3. አሁን ፣ እስከ ሁለቱ ድረስ የሚከተሉትን ያድርጉ i or j ዜሮ ይሆናል
    • አንድ [i]> = b [j] ከሆነ
      • አንድ [idx] = a [i] ፣ መቀነስ ይመድቡ i
    • ሌሎች
      • አንድ [idx] = b [j] ይመድቡ ፣ መቀነስ j
    • ቅነሳ መታወቂያ
  4. ከሁለቱም እኔ ወይም ጄ ዜሮ አይደለም ፣ ይህ ማለት አንዳንድ አካላት ገና ተዋህደዋል ማለት ነው። እነሱ ቀድሞውኑ በተደረደሩበት ሁኔታ ውስጥ እንደሚሆኑ በቀላሉ ከፊት ለፊቱ ወደ መጀመሪያው ድርድር እናዛቸዋለን ፡፡
  5. ቢሆንም i ዜሮ አይሆንም ፣
    1. አንድ [idx] = a [i] መድብ
    2. ቅነሳ መታወቂያi
  6. ቢሆንም j ዜሮ አይሆንም ፣
    1. አንድ [idx] = b [j] መድብ
    2. ቅነሳ መታወቂያ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 = የሁለተኛው ድርድር መጠን። ሁለቱን ድርድሮች አንድ ጊዜ ስናልፍ ፡፡

የቦታ ውስብስብነት

ኦ (1) ፣ በመጀመሪያው ድርድር ውስጥ ሁሉንም ንጥረ ነገሮች ስናከማች ፡፡ ስለዚህ ፣ አልጎሪዝም ነው በቦታው.