عناصر متمایز مشترک در همه ردیف های ماتریس را پیدا کنید


سطح دشواری سخت
اغلب در بلک راک Expedia JP مورگان سامسونگ اسنپدل یاترا ZOHO
هشی کردن ماتریس مرتب سازی

بیان مسأله

به ما یک ماتریس از تمام اعداد صحیح داده می شود. مسئله "یافتن عناصر متمایز مشترک برای همه ردیف های ماتریس" می خواهد همه عناصر مجزا را که ممکن است در همه ردیف های موجود در یک ماتریس مشترک باشد ، پیدا کند.

مثال

arr[]={ {11, 12, 3, 10},

{11, 5, 8, 3},

{7, 11, 3, 10},

{9, 10, 11, 3}}
3 11

توضیح: 3 و 11 دو عددی هستند که در هر ردیف در یک ماتریس معین متمایز هستند و همچنین مشترک هستند.

الگوریتم برای پیدا کردن عناصر متمایز مشترک در همه ردیف های یک ماتریس

1. Declare a Set “SETValue”.
2. Add all the values of the first row of a matrix into the “SETValue”.
3. Traverse the matrix from the second row of a given matrix.
  1. Declare a new set let’s say “temp”, every time for each row of a matrix.
    1. Add all the values of that particular row in “temp” Set.
  2. Iterate over the set “SETValue” in which we stored our first row values.
    1. Check if temp contains any of the value of SETValue.
      1. If it contains, then removes that value from the SETValue.
  3. If SETValue size is equal to 0, then break the loop.
4. Traverse SETValue and print all the values in it.

توضیح

با توجه به ماتریسی از اعداد صحیح. وظیفه ما کشف همه مقادیر ممکن یک ماتریس است که برای یکدیگر متمایز هستند. و همچنین در هر یک از ردیف های یک ماتریس مشترک است. ما در حل این س theال از Set Data Structure استفاده خواهیم کرد. این مجموعه ساختار داده به حذف یا عدم پذیرش عناصر کپی شده کمک می کند. ما ماتریس را از ردیف دوم ماتریس رد می کنیم. چون ردیف اول ما قبلاً به یک مجموعه اختصاص خواهیم یافت.

ما یک مجموعه را ابتدا SETValue اعلام می کنیم و تمام مقادیر ردیف اول ماتریس را به مجموعه اضافه می کنیم. این فقط به این دلیل است که ما باید تمام عناصری را که باید در همه ردیف ها مشترک باشند بررسی کنیم. بنابراین می توانیم از ردیف اول که به یک مجموعه به عنوان مرجع اختصاص داده می شود ، استفاده کنیم.

ما اکنون ماتریس را از عناصر ردیف دوم رد می کنیم زیرا ردیف اول را قبلاً پوشش داده ایم و اکنون از ردیف دوم یک ردیف جدید می گیریم تنظیم در واقع ، ساختار داده برای هر ردیف جدید از یک ماتریس داده شده در مسیر عبور ، ساختار داده جدیدی را در نظر خواهیم گرفت. زیرا ما باید آن عناصر خاص ردیف را در مجموعه جدیدی به نام "temp" ذخیره کنیم. سپس ما قصد داریم بررسی کنیم که آیا در صورت وجود مقدار SETValue در دما وجود دارد یا خیر ، آن عنصر را حذف می کنیم. همچنین ، ما یک شرط را برای بررسی مقدار استثنای اشاره گر پوچ قرار داده ایم. اگر اندازه مجموعه SETValue 0 شود ، حلقه را می شکند و خطایی در زمان اجرا وجود نخواهد داشت.

همانطور که عناصر را از SETValue حذف می کنیم ، پس از عبور از مقدار مقادیر خروجی در آن قرار داریم ، بنابراین این مقادیر را چاپ خواهیم کرد.

عناصر متمایز مشترک در همه ردیف های ماتریس را پیدا کنید

رمز

کد ++ C برای یافتن عناصر متمایز مشترک در همه ردیف های ماتریس

#include<unordered_set>
#include<iostream>

using namespace std;

const int MAX = 100;

void getDistinctCommonElements (int mat[][MAX], int n)
{
    unordered_set<int> SETValue;

    for (int i=0; i<n; i++)
        SETValue.insert(mat[0][i]);

    for (int i=1; i<n; i++)
    {
        unordered_set<int> temp;

        for (int j=0; j<n; j++)
            temp.insert(mat[i][j]);

        unordered_set<int>:: iterator itr;

        for (itr=SETValue.begin(); itr!=SETValue.end(); itr++)

            if (temp.find(*itr) == temp.end())
                SETValue.erase(*itr);

        if (SETValue.size() == 0)
            break;
    }
    unordered_set<int>:: iterator itr;
    for (itr=SETValue.begin(); itr!=SETValue.end(); itr++)
        cout << *itr << " ";
}
int main()
{
    int mat[][MAX] =  { {11, 12, 3, 10},
        {11, 5, 8, 3},
        {7, 11, 3, 1},
        {9, 0, 11, 3}
    };
    int n = 4;
    getDistinctCommonElements (mat, n);
    return 0;
}
3 11

کد جاوا برای یافتن عناصر متمایز مشترک در همه ردیف های ماتریس

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Collection;

class DistinctCommonElements
{
    public static void getDistinctCommonElements(int mat[][], int n)
    {
        Collection<Integer> removeElements = new LinkedList<Integer>();
        HashSet<Integer> SETValue=new HashSet<>();

        for (int i=0; i<n; i++)
            SETValue.add(mat[0][i]);

        for (int i=1; i<n; i++)
        {
            HashSet<Integer> temp= new HashSet<Integer>();
            for (int j=0; j<n; j++)
                temp.add(mat[i][j]);

            for(Integer element : SETValue)
                if(!(temp.contains(element)))
                    removeElements.add(element);

            SETValue.removeAll(removeElements);

            if (SETValue.size() == 0)
                break;
        }
        Iterator<Integer> itr=SETValue.iterator();
        while(itr.hasNext())
            System.out.print(itr.next()+" ");
    }
    public static void main(String [] args)
    {
        int mat[][] = { {11, 12, 3, 10},
            {11, 5, 8, 3},
            {7, 11, 3, 10},
            {9, 10, 11, 3}
        };
        int n = 4;
        getDistinctCommonElements (mat, n);
    }
}
3 11

تحلیل پیچیدگی

پیچیدگی زمان

در اینجا ما از دو حلقه تو در تو استفاده کرده ایم و استفاده از unordered_set / HashSet به ما پیچیدگی زمان چند جمله ای را می دهد. بر2) جایی که "n" اندازه ماتریس است.

پیچیدگی فضا

O (N) جایی که "n" اندازه ماتریس برای ذخیره عناصر ورودی و ذخیره در HashSet است.