دیئے گئے میٹرکس کی تمام قطاروں میں مشترکہ عناصر


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون سسکو ڈی ای شا اوپرا SAP لیبز Zoho
لڑی ہیش ہیکنگ میٹرکس

مسئلہ یہ بیان

"دیئے گئے میٹرکس کی تمام صفوں میں مشترکہ عناصر" یہ کہتے ہیں کہ ، آپ کو ایم * این کا میٹرکس دیا گیا ہے۔ مسئلے کے بیان میں O (M * N) وقت میں میٹرکس کی ہر صف میں دیئے گئے میٹرکس میں موجود تمام عام عناصر کو تلاش کرنے کے لئے کہا گیا ہے۔

مثال کے طور پر

arr[]={{12, 1, 4, 5, 9},

{3, 8, 0, 4, 1},

{2, 7, 4, 1, 5},

{6, 3, 1, 9, 4}}
1 4

وضاحت: 1 اور 4 میٹرکس کے واحد عنصر ہیں جو دیئے گئے میٹرکس کی ہر صف میں موجود ہیں۔

 

دیئے گئے میٹرکس کی تمام قطاروں میں مشترکہ عناصر تلاش کرنے کے لئے الگورتھم

1. Declare a map.
2. Assign all the values of a first row to 1 and stored into the map.
3. Traverse the matrix from the 2nd row of the matrix.
    1. Check if the map contains the current value of the matrix and also the current matrix’s value in a map should be equal to i.
    2. If true, then increase the value of the current matrix’s element frequency in a map by 1.
    3. Put the condition if this is the last row then print all those elements which are common in each row.

وضاحت

ہمیں ایم * این سائز کا میٹرکس دیا گیا ہے۔ ہمارا کام تمام عام عناصر کا پتہ لگانا ہے جو دیئے گئے میٹرکس کی ہر صف میں موجود ہیں۔ ہم ہیشنگ تکنیک کا استعمال کرکے اسے حل کریں گے۔ بولی نقطہ نظر کو استعمال کرنے میں ہم کوڈ سے زیادہ وقت کی پیچیدگی کا سامنا کرنا پڑے گا۔ لہذا ، ہم اسے O (M * N) وقت کی پیچیدگی میں حل کریں گے۔ ہم نقشہ کا اعلان کریں گے۔ اس نقشے میں ، ہم اقدار کو 1 سے شروع کریں گے اور پھر میٹرکس میں آگے والی اقدار کے ساتھ آگے بڑھیں گے۔

نقشہ دیکھیں ، ہم میٹرکس کی پہلی صف کے ساتھ شروع کریں گے اور صرف پہلی صف عناصر کی تمام اقدار کو 1 سے شروع کریں گے۔ اس کی وجہ یہ ہے کہ جب ہم میٹرکس میں دوسری صف میں جاتے ہیں۔ اور اگر ہمارے پاس عنصر a میں ہے نقشہ دوسری صف میں موجود کی طرح اس کا مطلب ہے کہ ہمیں ابھی کے لئے مشترکہ عنصر مل گیا ہے جو ابھی کے لئے صرف دو قطاروں میں موجود ہے۔

اب دوسری قطار سے میٹرکس کو تلاش کرنا شروع کریں ، ہم جانچ کریں گے کہ کیا ہر صف کا ہر عنصر نقشہ میں موجود ہے ، اگر وہ نقشہ میں موجود ہے تو پھر اس کا مطلب یہ ہے کہ یہ 2 ہےnd اس عنصر کا وقوعہ متوقع طور پر دوسری قطار میں میٹرکس میں ہوتا ہے۔ ہم یہ چیک کریں گے کہ اگر ہم نے جو عنصر منتخب کیا ہے اس کی موجودہ صف کے برابر ہے یا نہیں۔ ہم اس عنصر کی تعدد کی قیمت کو اپ ڈیٹ کریں گے اور نقشہ میں اس میں 1 اضافہ کریں گے۔ لہذا ہر تعاقب کے ل we ، ہم اس کی تعدد کو جانچ رہے ہیں اگر یہ قطار کے برابر ہے اس کا مطلب ہے کہ یہ تمام صفوں میں متواتر موجود ہے ، پھر جب ہم آخری صف میں گذریں گے تو ہم میٹرکس کے ان تمام اقدار کو چھاپ رہے ہیں۔

دیئے گئے میٹرکس کی تمام قطاروں میں مشترکہ عناصر

ضابطے

C ++ ایک دیئے گئے میٹرکس کی تمام قطاروں میں مشترکہ عناصر تلاش کرنے کے لئے کوڈ

#include<iostream>
#include<unordered_map>

#define M 4
#define N 5
using namespace std;


void getCommonElementinRow(int matrix[M][N])
{
    unordered_map<int, int> MAP;

    for (int j = 0; j < N; j++)
        MAP[matrix[0][j]] = 1;

    for (int i = 1; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (MAP[matrix[i][j]] == i)
            {
                MAP[matrix[i][j]] = i + 1;

                if (i==M-1)
                    cout << matrix[i][j] << " ";
            }
        }
    }
}
int main()
{
    int matrix[M][N] = {{12, 1, 4, 5, 9},
        {3, 8, 0, 4, 1},
        {2, 7, 4, 1, 5},
        {6, 3, 1, 9, 4}
    };

    getCommonElementinRow(matrix);

    return 0;
}
1 4

دیئے گئے میٹرکس کی تمام قطاروں میں مشترکہ عناصر تلاش کرنے کے لئے جاوا کوڈ

import java.util.HashMap;

class CommonElementsinRow
{
    private static int M = 4;
    private static int N =5;

    static void getCommonElementinRow(int matrix[][])
    {

        HashMap<Integer,Integer> MAP = new HashMap<>();

        for (int j = 0; j < N; j++)
            MAP.put(matrix[0][j],1);

        for (int i = 1; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (MAP.get(matrix[i][j]) != null && MAP.get(matrix[i][j]) == i)
                {

                    MAP.put(matrix[i][j], i + 1);

                    if (i == M - 1)
                        System.out.print(matrix[i][j] + " ");
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int matrix[][] =
        {
            {12, 1, 4, 5, 9},
            {3, 8, 0, 4, 1},
            {2, 7, 4, 1, 5},
            {6, 3, 1, 9, 4}
        };
        getCommonElementinRow(matrix);
    }
}
1 4

 

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (m * n) کہاں "ایم" اور "این" میٹرکس میں قطار اور کالم کی تعداد ہے۔ چونکہ ہم ہش میپ کا استعمال کرتے ہیں ہم O (1) وقت کی پیچیدگی میں اندراج اور دیگر کاروائیاں انجام دے سکتے ہیں۔ اس طرح یہ او (N * M) وقت کی پیچیدگی میں چلنے کے لئے الگورتھم بناتا ہے۔

خلائی پیچیدگی

O (m * n) کہاں "ایم" اور "این" میٹرکس میں قطار اور کالم کی تعداد ہے۔ چونکہ ابتدائی ان پٹ خود سائز N * M کا ہے ، لہذا ہم کہتے ہیں کہ خلائی پیچیدگی O (N * M) ہے۔