Рубрики

Объединить массив размером n в другой массив размером m + n

Есть два отсортированных массива. Первый имеет размер m + n, содержащий только m элементов. Другой имеет размер n и содержит n элементов. Объедините эти два массива в первый массив размером m + n так, чтобы выходные данные были отсортированы.

Вход: массив с m + n элементами (mPlusN []).

NA => Значение не заполнено / не доступно в массиве mPlusN []. Таких блоков массивов должно быть.

Вход: массив с n элементами (N []).

Вывод: N [] объединен с mPlusN [] (изменен mPlusN [])

Алгоритм:

Let first array be mPlusN[] and other array be N[]
1) Move m elements of mPlusN[] to end.
2) Start from nth element of mPlusN[] and 0th 
   element of N[] and merge them into mPlusN[].

Ниже приведена реализация вышеуказанного алгоритма:

C ++

// C ++ программа для объединения массива
// размер n в другой массив размером m + n
#include <bits/stdc++.h>

using namespace std;

  
/ * Предполагается, что -1 заполнено для мест

   где элемент недоступен * /

#define NA -1

  
/ * Функция для перемещения m элементов в

   конец массива mPlusN [] * /

void moveToEnd(int mPlusN[], int size)

{

   int j = size - 1;

   for (int i = size - 1; i >= 0; i--)

     if (mPlusN[i] != NA)

     {

        mPlusN[j] = mPlusN[i];

        j--;

     }

}

  
/ * Объединяет массив N [] размера n в

   массив mPlusN [] размером m + n * /

int merge(int mPlusN[], int N[], int m, int n)

{

   int i = n; / * Текущий индекс i / p части mPlusN [] * /

   int j = 0; / * Текущий индекс N [] * /

   int k = 0; / * Текущий индекс выхода mPlusN [] * /

   while (k < (m + n))

   {

    / * Взять элемент из mPlusN [], если

    а) стоимость выбранного элемента меньше

       и мы не достигли конца этого

    б) Мы достигли конца N [] * /

    if ((i < (m + n) && mPlusN[i] <= N[j]) || (j == n))

    {

        mPlusN[k] = mPlusN[i];

        k++;

        i++;

    }

    else // Иначе взять элемент из N []

    {

       mPlusN[k] = N[j];

       k++;

       j++;

    }

   }

}

  
/ * Утилита, которая печатает массив в строке * /

void printArray(int arr[], int size)

{

   for (int i = 0; i < size; i++)

   cout << arr[i] << " ";

  

   cout << endl;

}

  
/ * Функция драйвера для проверки вышеуказанных функций * /

int main()

{

   / * Инициализировать массивы * /

   int mPlusN[] = {2, 8, NA, NA, NA, 13, NA, 15, 20};

   int N[] = {5, 7, 9, 25};

     

   int n = sizeof(N) / sizeof(N[0]);

   int m = sizeof(mPlusN) / sizeof(mPlusN[0]) - n;

  

   / * Переместить элементы m в конце mPlusN * /

   moveToEnd(mPlusN, m + n);

  

   / * Объединить N [] в mPlusN [] * /

   merge(mPlusN, N, m, n);

  

   / * Распечатать результирующий mPlusN * /

   printArray(mPlusN, m+n);

  

   return 0;

}

С

#include <stdio.h>

  
/ * Предполагается, что -1 заполнено для мест, где элемент

   не доступен */

#define NA -1

  
/ * Функция для перемещения m элементов в конец массива mPlusN [] * /

void moveToEnd(int mPlusN[], int size)

{

  int i = 0, j = size - 1;

  for (i = size-1; i >= 0; i--)

    if (mPlusN[i] != NA)

    {

      mPlusN[j] = mPlusN[i];

      j--;

    }

}

  
/ * Объединяет массив N [] размера n в массив mPlusN []

   размером m + n * /

int merge(int mPlusN[], int N[], int m, int n)

{

  int i = n;  / * Текущий индекс i / p части mPlusN [] * /

  int j = 0; / * Текущий индекс N [] * /

  int k = 0; / * Текущий индекс выхода mPlusN [] * /

  while (k < (m+n))

  {

    / * Взять элемент из mPlusN [], если

       а) стоимость выбранного элемента меньше, и мы имеем

          не достиг конца этого

       б) Мы достигли конца N [] * /

    if ((i < (m+n) && mPlusN[i] <= N[j]) || (j == n))

    {

      mPlusN[k] = mPlusN[i];

      k++;

      i++;

    }

    else  // Иначе взять элемент из N []

    {

      mPlusN[k] = N[j];

      k++;

      j++;

    }

  }

}

  
/ * Утилита, которая печатает массив в строке * /

void printArray(int arr[], int size)

{

  int i;

  for (i=0; i < size; i++)

    printf("%d ", arr[i]);

  

  printf("\n");

}

  
/ * Функция драйвера для проверки вышеуказанных функций * /

int main()

{

  / * Инициализировать массивы * /

  int mPlusN[] = {2, 8, NA, NA, NA, 13, NA, 15, 20};

  int N[] = {5, 7, 9, 25};

  int n = sizeof(N)/sizeof(N[0]);

  int m = sizeof(mPlusN)/sizeof(mPlusN[0]) - n;

  

  / * Переместить элементы m в конце mPlusN * /

  moveToEnd(mPlusN, m+n);

  

  / * Объединить N [] в mPlusN [] * /

  merge(mPlusN, N, m, n);

  

  / * Распечатать результирующий mPlusN * /

  printArray(mPlusN, m+n);

  

  return 0;

}

Джава

class MergeArrays 

{

    / * Функция для перемещения m элементов в конец массива mPlusN [] * /

    void moveToEnd(int mPlusN[], int size) 

    {

        int i, j = size - 1;

        for (i = size - 1; i >= 0; i--) 

        {

            if (mPlusN[i] != -1

            {

                mPlusN[j] = mPlusN[i];

                j--;

            }

        }

    }

  

    / * Объединяет массив N [] размера n в массив mPlusN []

       размером m + n * /

    void merge(int mPlusN[], int N[], int m, int n) 

    {

        int i = n;

          

        / * Текущий индекс i / p части mPlusN [] * /

        int j = 0;

          

        / * Текущий индекс N [] * /

        int k = 0;

          

        / * Текущий индекс выхода mPlusN [] * /

        while (k < (m + n)) 

        {

            / * Взять элемент из mPlusN [], если

            а) стоимость выбранного элемента меньше, и мы имеем

                не достиг конца этого

            б) Мы достигли конца N [] * /

            if ((i < (m + n) && mPlusN[i] <= N[j]) || (j == n)) 

            {

                mPlusN[k] = mPlusN[i];

                k++;

                i++;

            

            else // Иначе взять элемент из N []

            {

                mPlusN[k] = N[j];

                k++;

                j++;

            }

        }

    }

  

    / * Утилита, которая печатает массив в строке * /

    void printArray(int arr[], int size) 

    {

        int i;

        for (i = 0; i < size; i++) 

            System.out.print(arr[i] + " ");

  

        System.out.println("");

    }

  

    public static void main(String[] args) 

    {

        MergeArrays mergearray = new MergeArrays();

          

        / * Инициализировать массивы * /

        int mPlusN[] = {2, 8, -1, -1, -1, 13, -1, 15, 20};

        int N[] = {5, 7, 9, 25};

        int n = N.length;

        int m = mPlusN.length - n;

  

        / * Переместить элементы m в конце mPlusN * /

        mergearray.moveToEnd(mPlusN, m + n);

  

        / * Объединить N [] в mPlusN [] * /

        mergearray.merge(mPlusN, N, m, n);

  

        / * Распечатать результирующий mPlusN * /

        mergearray.printArray(mPlusN, m + n);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# Предполагая, что -1 заполнено
# для мест где элемент
# не доступен

   

NA = -1

   
# Функция для перемещения m элементов
# в конце массива mPlusN []

def moveToEnd(mPlusN, size):

  

    i = 0

    j = size - 1

    for i in range(size-1, -1, -1):

        if (mPlusN[i] != NA):

      

            mPlusN[j] = mPlusN[i]

            j-=1

   
# Объединяет массив N []
# размера n в массив mPlusN []
№ размера m + n

def merge(mPlusN, N, m, n):

  

    i = # Текущий индекс i / p части mPlusN []

    j = 0  # Текущий индекс N []

    k = 0  # Текущий индекс вывода mPlusN []

    while (k < (m+n)):

      

        # Взять элемент из mPlusN [], если

        # а) стоимость выбранного

        # элемент меньше, и мы имеем

        # не достиг конца

        # b) Мы достигли конца N [] * /

        if ((i < (m+n) and mPlusN[i] <= N[j]) or (j == n)):

      

            mPlusN[k] = mPlusN[i]

            k+=1

            i+=1

      

        else# В противном случае взять элемент из N []

          

            mPlusN[k] = N[j]

            k+=1

            j+=1

   
# Утилита, которая печатает
# из массива в строке

def printArray(arr,size):

  

    for i in range(size):

        print(arr[i], " ", end="")

   

    print()

  

   
# Функция драйвера для
# тест над функциями

  
# Инициализировать массивы

mPlusN = [2, 8, NA, NA, NA, 13, NA, 15, 20]

N = [5, 7, 9, 25]

n = len(N)

  

m = len(mPlusN) - n

   
# Переместить элементы м
# в конце mPlusN

moveToEnd(mPlusN, m+n)

   
# Объединить N [] в mPlusN []
merge(mPlusN, N, m, n)

   
# Распечатать результирующий mPlusN

printArray(mPlusN, m+n)

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для объединения массива
// размер n в другой массив размером m + n

using System;

  

class GFG

{
/ * Функция для перемещения m элементов в

   конец массива mPlusN [] * /

public virtual void moveToEnd(int[] mPlusN, 

                              int size)

{

    int i, j = size - 1;

    for (i = size - 1; i >= 0; i--)

    {

        if (mPlusN[i] != -1)

        {

            mPlusN[j] = mPlusN[i];

            j--;

        }

    }

}

  
/ * Объединяет массив N [] размера n

   в массив mPlusN [] размером m + n * /

public virtual void merge(int[] mPlusN, int[] N,

                          int m, int n)

{

    int i = n;

  

    / * Текущий индекс i / p

       часть mPlusN [] * /

    int j = 0;

  

    / * Текущий индекс N [] * /

    int k = 0;

  

    / * Текущий индекс выхода mPlusN [] * /

    while (k < (m + n))

    {

        / * Взять элемент из mPlusN [], если

        а) стоимость выбранного элемента меньше

           и мы не достигли конца этого

        б) Мы достигли конца N [] * /

        if ((i < (m + n) &&

             mPlusN[i] <= N[j]) || (j == n))

        {

            mPlusN[k] = mPlusN[i];

            k++;

            i++;

        }

        else // Иначе взять элемент из N []

        {

            mPlusN[k] = N[j];

            k++;

            j++;

        }

    }

}

  
/ * Утилита, которая печатает

   массив в строке * /

public virtual void printArray(int[] arr,

                               int size)

{

    int i;

    for (i = 0; i < size; i++)

    {

        Console.Write(arr[i] + " ");

    }

  

    Console.WriteLine("");

}

  
// Код драйвера

public static void Main(string[] args)

{

    GFG mergearray = new GFG();

  

    / * Инициализировать массивы * /

    int[] mPlusN = new int[] {2, 8, -1, -1, -1,         

                              13, -1, 15, 20};

    int[] N = new int[] {5, 7, 9, 25};

    int n = N.Length;

    int m = mPlusN.Length - n;

  

    / * Переместить элементы м на

      конец mPlusN * /

    mergearray.moveToEnd(mPlusN, m + n);

  

    / * Объединить N [] в mPlusN [] * /

    mergearray.merge(mPlusN, N, m, n);

  

    / * Распечатать результирующий mPlusN * /

    mergearray.printArray(mPlusN, m + n);

}
}

  
// Этот код предоставлен Shrikant13

PHP

<?php
// PHP программа для объединения массивов
// размера n в другой массив
// размером m + n

  
/ * Предполагая, что -1 заполнено для
места, где элемент
нет в наличии */

$NA = -1;

  
/ * Функция для перемещения m элементов
в конце массива mPlusN [] * /

function moveToEnd(&$mPlusN, $size)

{

    global $NA;

    $j = $size - 1;

    for ($i = $size - 1; $i >= 0; $i--)

        if ($mPlusN[$i] != $NA)

        {

            $mPlusN[$j] = $mPlusN[$i];

            $j--;

        }

}

  
/ * Объединяет массив N [] размера n
в массив mPlusN [] размером m + n * /

function merge(&$mPlusN, &$N, $m, $n)

{

    $i = $n; / * Текущий индекс i / p

                часть mPlusN [] * /

    $j = 0;  / * Текущий индекс N [] * /

    $k = 0;  / * Текущий индекс

                выходной mPlusN [] * /

    while ($k < ($m + $n))

    {

        / * Взять элемент из mPlusN [], если

        а) стоимость выбранного элемента

           меньше и у нас нет

           достиг конца этого

        б) Мы достигли конца N [] * /

        if (($i < ($m + $n) &&

             $mPlusN[$i] <= $N[$j]) || ($j == $n))

        {

            $mPlusN[$k] = $mPlusN[$i];

            $k++;

            $i++;

        }

        else // Иначе взять элемент из N []

        {

            $mPlusN[$k] = $N[$j];

            $k++;

            $j++;

        }

}
}

  
/ * Утилита, которая печатает

   массив в строке * /

function printArray(&$arr, $size)

{

    for ($i = 0; $i < $size; $i++)

    echo $arr[$i] . " ";

      

    echo "\n";

}

  
// Код драйвера

  
/ * Инициализировать массивы * /

$mPlusN = array(2, 8, $NA, $NA, $NA,

                13, $NA, 15, 20);

$N = array(5, 7, 9, 25);

      

$n = sizeof($N);

$m = sizeof($mPlusN) - $n;

  
/ * Переместить элементы m

   в конце mPlusN * /

moveToEnd($mPlusN, $m + $n);

  
/ * Объединить N [] в mPlusN [] * /

merge($mPlusN, $N, $m, $n);

  
/ * Распечатать результирующий mPlusN * /

printArray($mPlusN, $m+$n);

  
// Этот код добавлен
// ChitraNayal
?>

Выход:

2 5 7 8 9 13 15 20 25

Сложность времени: O (m + n)

Пожалуйста, напишите комментарий, если вы обнаружите какую-либо ошибку в вышеуказанной программе или лучший способ решить ту же проблему.

Рекомендуемые посты:

Объединить массив размером n в другой массив размером m + n

0.00 (0%) 0 votes