سه آرایه مرتب شده به صورت نزولی (غیر صعودی)، داده شده است. هدف، چاپ کردن همه عناصر مشترک در این سه آرایه است. مثال‌های زیر در این راستا قابل توجه هستند.

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)‎ است که در آن، n2 ،n1 و n3 به ترتیب سایز آرایه‌های []ar2[] ،ar1 و []ar3 هستند. راهکار بالا نیازمند فضای اضافی و دو حلقه است؛ می‌توان عناصر مشترک را با استفاده از یک حلقه و بدون فضای اضافی نیز پیدا کرد. در اینجا، یک حلقه اجرا و سه آرایه پیمایش می‌شوند. فرض می‌شود که عنصر کنونی پیمایش شده در []ar1 عنصر x و در آرایه []ar2 عنصر y و در آرایه []ar3 عنصر z باشد. می‌توان موارد زیر را درون حلقه داشت:

• اگر y ،x و z مشابه باشند، می‌توان به راحتی یکی از آن‌ها را به عنوان عناصر مشترک چاپ کرد و در سه آرایه به پیش رفت.
• در غیر این صورت، اگر x < y، می‌توان در آرایه ar1[]‎ به پیشرفت، زیرا x یک عنصر مشترک نیست.
• اگر x > z و y > z× می‌توان به سادگی در آرایه []ar3 پیش رفت، زیرا z نمی‌تواند یک عنصر مشترک باشد.

در تصویر زیر، خروجی حاصل از اجرای الگوریتم‌های بالا ارائه شده است.

برای مشاهده تصویر در اندازه کامل، کلیک کنید.

در ادامه، پیاده‌سازی رویکرد بالا در زبان‌های برنامه‌نویسی گوناگون انجام شده است.

برنامه پیدا کردن عناصر مشترک در آرایه های مرتب در ++C

// C++ program to print common elements in three arrays 
#include <bits/stdc++.h> 
using namespace std; 
  
// This function prints common elements in ar1 
void findCommon(int ar1[], int ar2[], int ar3[], int n1, int n2, int n3) 
{ 
    // Initialize starting indexes for ar1[], ar2[] and ar3[] 
    int i = 0, j = 0, k = 0; 
  
    // Iterate through three arrays while all arrays have elements 
    while (i < n1 && j < n2 && k < n3) 
    { 
         // If x = y and y = z, print any of them and move ahead  
         // in all arrays 
         if (ar1[i] == ar2[j] && ar2[j] == ar3[k]) 
         {   cout << ar1[i] << " ";   i++; j++; k++; } 
  
         // x < y 
         else if (ar1[i] < ar2[j]) 
             i++; 
  
         // y < z 
         else if (ar2[j] < ar3[k]) 
             j++; 
  
         // We reach here when x > y and z < y, i.e., z is smallest 
         else
             k++; 
    } 
} 
  
// Driver program to test above function 
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 program to find common elements in three arrays 
class FindCommon 
{ 
    // This function prints common elements in ar1 
    void findCommon(int ar1[], int ar2[], int ar3[]) 
    { 
        // Initialize starting indexes for ar1[], ar2[] and ar3[] 
        int i = 0, j = 0, k = 0; 
  
        // Iterate through three arrays while all arrays have elements 
        while (i < ar1.length && j < ar2.length && k < ar3.length) 
        { 
             // If x = y and y = z, print any of them and move ahead 
             // in all arrays 
             if (ar1[i] == ar2[j] && ar2[j] == ar3[k]) 
             {   System.out.print(ar1[i]+" ");   i++; j++; k++; } 
  
             // x < y 
             else if (ar1[i] < ar2[j]) 
                 i++; 
  
             // y < z 
             else if (ar2[j] < ar3[k]) 
                 j++; 
  
             // We reach here when x > y and z < y, i.e., z is smallest 
             else
                 k++; 
        } 
    } 
  
    // Driver code to test above 
    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); 
    } 
} 
  
/*This code is contributed by Rajat Mishra */

برنامه پیدا کردن عناصر مشترک در آرایه های مرتب در پایتون

# Python function to print common elements in three sorted arrays 
def findCommon(ar1, ar2, ar3, n1, n2, n3): 
      
    # Initialize starting indexes for ar1[], ar2[] and ar3[] 
    i, j, k = 0, 0, 0
      
    # Iterate through three arrays while all arrays have elements     
    while (i < n1 and j < n2 and k< n3): 
          
        # If x = y and y = z, print any of them and move ahead  
        # in all arrays 
        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
          
        # We reach here when x > y and z < y, i.e., z is smallest     
        else: 
            k += 1
  
# Driver program to check above function 
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) 
  
# This code is contributed by __Devesh Agrawal__

برنامه پیدا کردن عناصر مشترک در آرایه های مرتب در #C

// C# program to find common elements in 
// three arrays 
using System; 
  
class GFG { 
      
    // This function prints common element 
    // s in ar1 
    static void findCommon(int []ar1, int []ar2, 
                                      int []ar3) 
    { 
          
        // Initialize starting indexes for  
        // ar1[], ar2[] and ar3[] 
        int i = 0, j = 0, k = 0; 
  
        // Iterate through three arrays while  
        // all arrays have elements 
        while (i < ar1.Length && j < ar2.Length 
                              && k < ar3.Length) 
        { 
              
            // If x = y and y = z, print any of 
            // them and move ahead in all arrays 
            if (ar1[i] == ar2[j] &&  
                               ar2[j] == ar3[k]) 
            {  
                Console.Write(ar1[i] + " "); 
                i++; 
                j++; 
                k++; 
            } 
  
            // x < y 
            else if (ar1[i] < ar2[j]) 
                i++; 
  
            // y < z 
            else if (ar2[j] < ar3[k]) 
                j++; 
  
            // We reach here when x > y and 
            // z < y, i.e., z is smallest 
            else
                k++; 
        } 
    } 
  
    // Driver code to test above 
    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, 
                             ۷۰, ۸۰, ۱۲۰}; 
  
        Console.Write("Common elements are "); 
          
        findCommon(ar1, ar2, ar3); 
    } 
} 
  
// This code is contributed by Sam007.

برنامه پیدا کردن عناصر مشترک در آرایه های مرتب در PHP

<?php 
// PHP program to print common elements 
// in three arrays 
  
// This function prints common elements 
// in ar1 
function findCommon( $ar1, $ar2, $ar3, 
                         $n1, $n2, $n3) 
{ 
      
    // Initialize starting indexes for 
    // ar1[], ar2[] and ar3[] 
    $i = 0; $j = 0; $k = 0; 
  
    // Iterate through three arrays while 
    // all arrays have elements 
    while ($i < $n1 && $j < $n2 && $k < $n3) 
    { 
          
        // If x = y and y = z, print any 
        // of them and move ahead in all  
        // arrays 
        if ($ar1[$i] == $ar2[$j] && 
                      $ar2[$j] == $ar3[$k]) 
        { 
            echo $ar1[$i] , " "; 
            $i++; 
            $j++; 
            $k++;  
        } 
  
        // x < y 
        else if ($ar1[$i] < $ar2[$j]) 
            $i++; 
  
        // y < z 
        else if ($ar2[$j] < $ar3[$k]) 
            $j++; 
  
        // We reach here when x > y and 
        // z < y, i.e., z is smallest 
        else
            $k++; 
    } 
} 
  
// Driver program to test above function 
    $ar1 = array(1, 5, 10, 20, 40, 80); 
    $ar2 = array(6, 7, 20, 80, 100); 
    $ar3 = array(3, 4, 15, 20, 30, 70,  
                                ۸۰, ۱۲۰); 
    $n1 = count($ar1); 
    $n2 = count($ar2); 
    $n3 = count($ar3); 
  
    echo "Common Elements are "; 
      
    findCommon($ar1, $ar2, $ar3,$n1, $n2, $n3); 
      
// This code is contributed by anuj_67. 
?>

خروجی قطعه کدهای بالا به صورت زیر است.

Common Elements are 20 80

پیچیدگی زمانی راهکار بالا از درجه O(n1 + n2 + n3)‎ است. در بدترین حالت، آرایه‌ای با بزرگ‌ترین اندازه ممکن است همه عناصر کوچک و آرایه سایز متوسط همه عناصر متوسط را داشته باشد.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• معرفی منابع آموزش ویدئویی هوش مصنوعی به زبان فارسی و انگلیسی
• زبان برنامه‌نویسی پایتون (Python) — از صفر تا صد
• آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس

منبع[+]