Рубрики

Найти общие элементы в трех отсортированных массивах

Массивы, Поиск

Учитывая три массива, отсортированные в неубывающем порядке, выведите все общие элементы в этих массивах.

Примеры:

Input:
ar1[] = {1, 5, 10, 20, 40, 80}
ar2[] = {6, 7, 20, 80, 100}
ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}
Output: 20, 80

Input:
ar1[] = {1, 5, 5}
ar2[] = {3, 4, 5, 5, 10}
ar3[] = {5, 5, 10, 20}
Output: 5, 5

Простое решение — сначала найти пересечение двух массивов и сохранить пересечение во временном массиве, а затем найти пересечение третьего массива и временного массива.

Временная сложность этого решения составляет O (n1 + n2 + n3), где n1, n2 и n3 — размеры ar1 [], ar2 [] и ar3 [] соответственно.

Приведенное выше решение требует дополнительного пространства и двух циклов, мы можем найти общие элементы, используя один цикл и без дополнительного пространства. Идея похожа на пересечение двух массивов . Подобно циклу двух массивов, мы запускаем цикл и пересекаем три массива.

Пусть текущий элемент, пройденный в ar1 [], равен x, в ar2 [] — y, а в ar3 [] — z. Мы можем иметь следующие случаи внутри цикла.

  • Если x, y и z одинаковы, мы можем просто напечатать любой из них как общий элемент и двигаться вперед во всех трех массивах.
  • Иначе если х
  • Иначе, если x> z и y> z), мы можем просто двигаться вперед в ar3 [], так как z не может быть общим элементом.

Ниже приведен пробный запуск вышеуказанного подхода:

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

C ++

// C ++ программа для печати общих элементов в трех массивах
#include <iostream>

using namespace std;

  
// Эта функция печатает общие элементы в ar1

void findCommon(int ar1[], int ar2[], int ar3[], int n1, int n2, int n3)

{

    // Инициализировать начальные индексы для ar1 [], ar2 [] и ar3 []

    int i = 0, j = 0, k = 0;

  

    // Итерация по трем массивам, в то время как все массивы имеют элементы

    while (i < n1 && j < n2 && k < n3)

    {

         // Если x = y и y = z, выведите любой из них и двигайтесь вперед

         // во всех массивах

         if (ar1[i] == ar2[j] && ar2[j] == ar3[k])

         {   cout << ar1[i] << " ";   i++; j++; k++; }

  

         // х <у

         else if (ar1[i] < ar2[j])

             i++;

  

         // y <z

         else if (ar2[j] < ar3[k])

             j++;

  

         // Мы достигаем здесь, когда x> y и z <y, т.е. z наименьшее

         else

             k++;

    }

}

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

int main()

{

    int ar1[] = {1, 5, 10, 20, 40, 80};

    int ar2[] = {6, 7, 20, 80, 100};

    int ar3[] = {3, 4, 15, 20, 30, 70, 80, 120};

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

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

    int n3 = sizeof(ar3)/sizeof(ar3[0]);

  

    cout << "Common Elements are ";

    findCommon(ar1, ar2, ar3, n1, n2, n3);

    return 0;

}

Джава

// Java-программа для поиска общих элементов в трех массивах

class FindCommon

{

    // Эта функция печатает общие элементы в ar1

    void findCommon(int ar1[], int ar2[], int ar3[])

    {

        // Инициализировать начальные индексы для ar1 [], ar2 [] и ar3 []

        int i = 0, j = 0, k = 0;

  

        // Итерация по трем массивам, в то время как все массивы имеют элементы

        while (i < ar1.length && j < ar2.length && k < ar3.length)

        {

             // Если x = y и y = z, выведите любой из них и двигайтесь вперед

             // во всех массивах

             if (ar1[i] == ar2[j] && ar2[j] == ar3[k])

             {   System.out.print(ar1[i]+" ");   i++; j++; k++; }

  

             // х <у

             else if (ar1[i] < ar2[j])

                 i++;

  

             // y <z

             else if (ar2[j] < ar3[k])

                 j++;

  

             // Мы достигаем здесь, когда x> y и z <y, т.е. z наименьшее

             else

                 k++;

        }

    }

  

    // Код драйвера для проверки выше

    public static void main(String args[])

    {

        FindCommon ob = new FindCommon();

  

        int ar1[] = {1, 5, 10, 20, 40, 80};

        int ar2[] = {6, 7, 20, 80, 100};

        int ar3[] = {3, 4, 15, 20, 30, 70, 80, 120};

  

        System.out.print("Common elements are ");

        ob.findCommon(ar1, ar2, ar3);

    }

}

  
/ * Этот код предоставлен Раджатом Мишрой * /

питон

# Функция Python для печати общих элементов в трех отсортированных массивах

def findCommon(ar1, ar2, ar3, n1, n2, n3):

      

    # Инициализировать начальные индексы для ar1 [], ar2 [] и ar3 []

    i, j, k = 0, 0, 0

      

    # Итерация по трем массивам, в то время как все массивы имеют элементы

    while (i < n1 and j < n2 and k< n3):

          

        # Если x = y и y = z, выведите любой из них и двигайтесь вперед

        # во всех массивах

        if (ar1[i] == ar2[j] and ar2[j] == ar3[k]):

            print ar1[i],

            i += 1

            j += 1

            k += 1

          

        # x <y

        elif ar1[i] < ar2[j]:

            i += 1

              

        # y <z

        elif ar2[j] < ar3[k]:

            j += 1

          

        # Мы достигаем здесь, когда x> y и z <y, т.е. z наименьшее

        else:

            k += 1

  
# Программа драйвера для проверки вышеуказанной функции

ar1 = [1, 5, 10, 20, 40, 80]

ar2 = [6, 7, 20, 80, 100]

ar3 = [3, 4, 15, 20, 30, 70, 80, 120]

n1 = len(ar1)

n2 = len(ar2)

n3 = len(ar3)

print "Common elements are",

findCommon(ar1, ar2, ar3, n1, n2, n3)

  
# Этот код предоставлен __Devesh Agrawal__

C #

// C # программа для поиска общих элементов в
// три массива

using System;

  

class GFG {

      

    // Эта функция печатает общий элемент

    // s в ar1

    static void findCommon(int []ar1, int []ar2,

                                      int []ar3)

    {

          

        // Инициализировать начальные индексы для

        // ar1 [], ar2 [] и ar3 []

        int i = 0, j = 0, k = 0;

  

        // Перебираем три массива, пока

        // все массивы имеют элементы

        while (i < ar1.Length && j < ar2.Length

                              && k < ar3.Length)

        {

              

            // Если x = y и y = z, выведите любое из

            // их и двигаться вперед во всех массивах

            if (ar1[i] == ar2[j] && 

                               ar2[j] == ar3[k])

            { 

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

                i++;

                j++;

                k++;

            }

  

            // х <у

            else if (ar1[i] < ar2[j])

                i++;

  

            // y <z

            else if (ar2[j] < ar3[k])

                j++;

  

            // Мы достигаем здесь, когда x> y и

            // z <y, т. е. z наименьшее

            else

                k++;

        }

    }

  

    // Код драйвера для проверки выше

    public static void Main()

    {

          

        int []ar1 = {1, 5, 10, 20, 40, 80};

        int []ar2 = {6, 7, 20, 80, 100};

        int []ar3 = {3, 4, 15, 20, 30,

                             70, 80, 120};

  

        Console.Write("Common elements are ");

          

        findCommon(ar1, ar2, ar3);

    }

}

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

PHP

<?php
// PHP программа для печати общих элементов
// в трех массивах

  
// Эта функция печатает общие элементы
// в ar1

function findCommon( $ar1, $ar2, $ar3,

                         $n1, $n2, $n3)

{

      

    // Инициализировать начальные индексы для

    // ar1 [], ar2 [] и ar3 []

    $i = 0; $j = 0; $k = 0;

  

    // Перебираем три массива, пока

    // все массивы имеют элементы

    while ($i < $n1 && $j < $n2 && $k < $n3)

    {

          

        // Если x = y и y = z, выведите любое

        // из них и двигаться вперед во всех

        // массивы

        if ($ar1[$i] == $ar2[$j] &&

                      $ar2[$j] == $ar3[$k])

        {

            echo $ar1[$i] , " ";

            $i++;

            $j++;

            $k++; 

        }

  

        // х <у

        else if ($ar1[$i] < $ar2[$j])

            $i++;

  

        // y <z

        else if ($ar2[$j] < $ar3[$k])

            $j++;

  

        // Мы достигаем здесь, когда x> y и

        // z <y, т. е. z наименьшее

        else

            $k++;

    }

}

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

    $ar1 = array(1, 5, 10, 20, 40, 80);

    $ar2 = array(6, 7, 20, 80, 100);

    $ar3 = array(3, 4, 15, 20, 30, 70, 

                                80, 120);

    $n1 = count($ar1);

    $n2 = count($ar2);

    $n3 = count($ar3);

  

    echo "Common Elements are ";

      

    findCommon($ar1, $ar2, $ar3,$n1, $n2, $n3);

      
// Этот код предоставлен anuj_67.
?>


Выход:

Common Elements are 20 80

Временная сложность вышеуказанного решения составляет O (n1 + n2 + n3). В худшем случае массив самого большого размера может иметь все маленькие элементы, а массив среднего размера — все средние элементы.

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

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

Найти общие элементы в трех отсортированных массивах

0.00 (0%) 0 votes