Рубрики

Объединить два отсортированных массива с O (1) дополнительным пробелом

Нам дают два отсортированных массива. Нам нужно объединить эти два массива так, чтобы начальные числа (после полной сортировки) были в первом массиве, а оставшиеся числа были во втором массиве. Допускается дополнительное пространство в O (1).

Пример:

Input: ar1[] = {10};
       ar2[] = {2, 3};
Output: ar1[] = {2}
        ar2[] = {3, 10}  

Input: ar1[] = {1, 5, 9, 10, 15, 20};
       ar2[] = {2, 3, 8, 13};
Output: ar1[] = {1, 2, 3, 5, 8, 9}
        ar2[] = {10, 13, 15, 20} 

Эта задача проста и O (m + n), если нам разрешено использовать дополнительное пространство. Но это становится действительно сложным, когда дополнительное пространство не разрешено и не представляется возможным менее чем за O (m * n) время наихудшего случая.

Идея состоит в том, чтобы начать с последнего элемента ar2 [] и искать его в ar1 []. Если в ar1 [] есть больший элемент, то мы перемещаем последний элемент ar1 [] в ar2 []. Чтобы отсортировать ar1 [] и ar2 [], нам нужно поместить последний элемент ar2 [] в правильное место в ar1 []. Для этого мы можем использовать тип вставки Sorttion Sort . Ниже приведен алгоритм:

1) Iterate through every element of ar2[] starting from last 
   element. Do following for every element ar2[i]
    a) Store last element of ar1[i]: last = ar1[i]
    b) Loop from last element of ar1[] while element ar1[j] is 
       smaller than ar2[i].
          ar1[j+1] = ar1[j] // Move element one position ahead
          j--
    c) If any element of ar1[] was moved or (j != m-1)
          ar1[j+1] = ar2[i] 
          ar2[i] = last  

В вышеуказанном цикле элементы в ar1 [] и ar2 [] всегда сохраняются отсортированными.

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

C ++

// C ++ программа для объединения двух отсортированных массивов с O (1) дополнительным пробелом.
#include <bits/stdc++.h>

using namespace std;

  
// Объединяем ar1 [] и ar2 [] с O (1) дополнительным пробелом

void merge(int ar1[], int ar2[], int m, int n)

{

    // Перебираем все элементы ar2 [], начиная с

    // последний элемент

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

    {

        / * Найти наименьший элемент больше, чем ar2 [i]. Переместить все

           элементы на одну позицию впереди до наименьшего большего

           элемент не найден * /

        int j, last = ar1[m-1];

        for (j=m-2; j >= 0 && ar1[j] > ar2[i]; j--)

            ar1[j+1] = ar1[j];

  

        // Если бы был больший элемент

        if (j != m-2 || last > ar2[i])

        {

            ar1[j+1] = ar2[i];

            ar2[i] = last;

        }

    }

}

  
// Драйвер программы

int main(void)

{

    int ar1[] = {1, 5, 9, 10, 15, 20};

    int ar2[] = {2, 3, 8, 13};

    int m = sizeof(ar1)/sizeof(ar1[0]);

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

    merge(ar1, ar2, m, n);

  

    cout << "After Merging nFirst Array: ";

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

        cout << ar1[i] << " ";

    cout << "nSecond Array: ";

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

        cout << ar2[i] << " ";

   return 0;

}

Джава

// Java программа для объединения двух
// отсортированные массивы с O (1) дополнительным пробелом.

  

import java.util.Arrays;

  

class Test

{

    static int arr1[] = new int[]{1, 5, 9, 10, 15, 20};

    static int arr2[] = new int[]{2, 3, 8, 13};

      

    static void merge(int m, int n)

    {

        // Перебираем все элементы ar2 [], начиная с

        // последний элемент

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

        {

            / * Найти наименьший элемент больше, чем ar2 [i]. Переместить все

               элементы на одну позицию впереди до наименьшего большего

               элемент не найден * /

            int j, last = arr1[m-1];

            for (j=m-2; j >= 0 && arr1[j] > arr2[i]; j--)

                arr1[j+1] = arr1[j];

       

            // Если бы был больший элемент

            if (j != m-2 || last > arr2[i])

            {

                arr1[j+1] = arr2[i];

                arr2[i] = last;

            }

        }

    }

      

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

    public static void main(String[] args) 

    {

        merge(arr1.length,arr2.length);

        System.out.print("After Merging nFirst Array: ");

        System.out.println(Arrays.toString(arr1));

        System.out.print("Second Array:  ");

        System.out.println(Arrays.toString(arr2));

    }

}

python3

# Python программа для слияния
# два отсортированных массива
# с O (1) дополнительным пробелом.

  
# Объединить ar1 [] и ar2 []
# с O (1) дополнительным пробелом

def merge(ar1, ar2, m, n):

  

    # Перебирать все

    # элементы ar2 [] начиная с

    # последний элемент

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

      

        # Найти самый маленький элемент

        # больше чем ar2 [i]. Переместить все

        # элементы на одну позицию впереди

        # до наименьшего большего

        # элемент не найден

        last = ar1[m-1]

        j=m-2

        while(j >= 0 and ar1[j] > ar2[i]):

            ar1[j+1] = ar1[j]

            j-=1

   

        # Если бы был больший элемент

        if (j != m-2 or last > ar2[i]):

          

            ar1[j+1] = ar2[i]

            ar2[i] = last

   
# Драйверная программа

  

ar1 = [1, 5, 9, 10, 15, 20]

ar2 = [2, 3, 8, 13]

m = len(ar1)

n = len(ar2)

  
merge(ar1, ar2, m, n)

   

print("After Merging \nFirst Array:", end="")

for i in range(m):

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

  

print("\nSecond Array: ", end="")

for i in range(n):

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

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

C #

// C # программа для объединения двух
// отсортированные массивы с O (1) дополнительным пробелом.

using System;

  
// Java программа для объединения двух
// отсортированные массивы с O (1) дополнительным пробелом.

  

  

public class Test 

    static int []arr1 = new int[]{1, 5, 9, 10, 15, 20}; 

    static int []arr2 = new int[]{2, 3, 8, 13}; 

      

    static void merge(int m, int n) 

    

        // Перебираем все элементы ar2 [], начиная с

        // последний элемент

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

        

            / * Найти наименьший элемент больше, чем ar2 [i]. Переместить все

            элементы на одну позицию впереди до наименьшего большего

            элемент не найден * /

            int j, last = arr1[m-1]; 

            for (j=m-2; j >= 0 && arr1[j] > arr2[i]; j--) 

                arr1[j+1] = arr1[j]; 

      

            // Если бы был больший элемент

            if (j != m-2 || last > arr2[i]) 

            

                arr1[j+1] = arr2[i]; 

                arr2[i] = last; 

            

        

    

      

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

    public static void Main() 

    

        merge(arr1.Length,arr2.Length); 

        Console.Write("After Merging \nFirst Array: "); 

        for(int i =0; i< arr1.Length;i++){

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

        }

        Console.Write("\nSecond Array: "); 

        for(int i =0; i< arr2.Length;i++){

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

        }

    

  
/ * Этот код предоставлен 29AjayKumar * /

PHP

<?php 
// PHP-программа для объединения двух отсортированных массивов с O (1) дополнительным пробелом.

   
// Объединяем ar1 [] и ar2 [] с O (1) дополнительным пробелом

function merge(&$ar1, &$ar2, $m, $n)

{

    // Перебираем все элементы ar2 [], начиная с

    // последний элемент

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

    {

        / * Найти наименьший элемент больше, чем ar2 [i]. Переместить все

           элементы на одну позицию впереди до наименьшего большего

           элемент не найден * /

        $last = $ar1[$m-1];

        for ($j = $m-2; $j >= 0 && $ar1[$j] > $ar2[$i]; $j--)

            $ar1[$j+1] = $ar1[$j];

   

        // Если бы был больший элемент

        if ($j != $m-2 || $last > $ar2[$i])

        {

            $ar1[$j+1] = $ar2[$i];

            $ar2[$i] = $last;

        }

    }

}

   
// Драйвер программы

  

$ar1 = array(1, 5, 9, 10, 15, 20);

$ar2 = array(2, 3, 8, 13);

$m = sizeof($ar1)/sizeof($ar1[0]);

$n = sizeof($ar2)/sizeof($ar2[0]);

merge($ar1, $ar2, $m, $n);

  

echo "After Merging \nFirst Array: ";

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

    echo $ar1[$i] . " ";

echo "\nSecond Array: ";

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

    echo $ar2[$i] ." ";

return 0;

?>


Выход:

After Merging 
First Array: 1 2 3 5 8 9 
Second Array: 10 13 15 20 

Сложность времени: сложность времени кода / алгоритма в наихудшем случае равна O (m * n). Худший случай происходит, когда все элементы ar1 [] больше, чем все элементы ar2 [].

Иллюстрация:

<! — Начальные массивы:
ar1 [] = {1, 5, 9, 10, 15, 20};
ar2 [] = {2, 3, 8, 13 };

После первой итерации:
ar1 [] = {1, 5, 9, 10, 13, 15};
ar2 [] = {2, 3, 8 , 20};
// 20 перемещено из ar1 [] в ar2 []
// 13 из ar2 [] вставляется в ar1 []

После второй итерации:
ar1 [] = {1, 5, 8, 9, 10, 13};
ar2 [] = {2, 3 , 15, 20};
// 15 перемещено из ar1 [] в ar2 []
// 8 из ar2 [] вставляется в ar1 []

После третьей итерации:
ar1 [] = {1, 3, 5, 8, 9, 10};
ar2 [] = { 2 , 13, 15, 20};
// 13 перемещено из ar1 [] в ar2 []
// 3 из ar2 [] вставляется в ar1 []

После четвертой итерации:
ar1 [] = {1, 2, 3, 5, 8, 9};
ar2 [] = {10, 13, 15, 20};
// 10 перемещено из ar1 [] в ar2 []
// 2 из ar2 [] вставляется в ar1 []
->

Эффективное объединение двух отсортированных массивов с O (1) дополнительным пространством

Статьи по Теме :
Объединить два отсортированных массива
Объединить k отсортированных массивов | Комплект 1

Спасибо Shubham Chauhan за предложенное решение. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Объединить два отсортированных массива с O (1) дополнительным пробелом

0.00 (0%) 0 votes