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


سطح دشواری متوسط
اغلب در آمازون سیسکو دی شاو اپرا آزمایشگاههای SAP ZOHO
صف مخلوط هشی کردن ماتریس

بیان مسأله

مسئله "عناصر مشترک در تمام ردیف های ماتریس معین" بیان می کند که ، به شما یک ماتریس M * N داده می شود. بیانیه مسئله می خواهد تمام عناصر مشترک در یک ماتریس داده شده در هر ردیف از ماتریس را در زمان 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.

توضیح

به ما یک ماتریس اندازه M * N داده می شود. وظیفه ما کشف همه عناصر مشترک است که در هر ردیف از ماتریس داده شده نیز وجود دارد. ما با استفاده از تکنیک هش کردن این مشکل را حل خواهیم کرد. استفاده از رویکرد ساده لوحانه پیچیدگی زمان بیشتری نسبت به این کد برای ما دارد. بنابراین ، ما آن را در پیچیدگی زمانی O (M * N) حل خواهیم کرد. ما نقشه را اعلام خواهیم کرد. در آن نقشه ، مقادیر را به 1 مقداردهی می کنیم و سپس مقادیر پیش رو را در یک ماتریس ادامه می دهیم.

یک نقشه بردارید ، ما با ردیف اول ماتریس شروع می کنیم و تمام مقادیر فقط عناصر ردیف اول را به 1 می رسانیم. این بدان دلیل است که وقتی برای ردیف دوم ماتریس عبور می کنیم. و اگر عنصر را در a داشته باشیم نقشه همان موجود در ردیف دوم. این بدان معنی است که ما عنصر مشترک فعلی را پیدا کرده ایم که در حال حاضر فقط در دو ردیف وجود دارد.

اکنون از ردیف دوم شروع به پیمایش ماتریس کنید ، بررسی خواهیم کرد که آیا هر عنصر از هر ردیف در نقشه وجود دارد یا خیر ، اگر در نقشه وجود داشته باشد ، به این معنی است که این 2 استnd وقوع آن عنصر در یک ماتریس به طور متوالی در یک ردیف دوم. ما بررسی خواهیم کرد که آیا هر فرکانس عنصری را که انتخاب کردیم برابر با ردیف فعلی است یا خیر. ما مقدار فرکانس آن عنصر را به روز کرده و 1 در نقشه افزایش می دهیم. بنابراین برای هر پیمایش ، ما فرکانس آن را بررسی خواهیم کرد اگر برابر با ردیف i باشد ، به این معنی است که به طور متوالی در همه ردیف ها وجود دارد ، سپس وقتی در ردیف آخر ردیف هستیم ، تمام مقادیر ماتریس را چاپ خواهیم کرد.

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

رمز

کد ++ 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) جایی که "متر" و "n" تعداد سطرها و ستون های ماتریس است. از آنجا که ما از HashMap استفاده می کنیم ، می توانیم عملیات درج و عملیات دیگر را با پیچیدگی زمان O (1) انجام دهیم. بنابراین این یک الگوریتم را برای اجرا در پیچیدگی زمان O (N * M) ایجاد می کند.

پیچیدگی فضا

O (m * n) جایی که "متر" و "n" تعداد سطرها و ستون های ماتریس است. از آنجا که ورودی اولیه خودش اندازه N * M است ، می گوییم پیچیدگی فضا O (N * M) است.