عام عناصر ڏنل ڏنل ميٽرڪس جي سڀني قطارن ۾


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon Cisco ڊي شاه ناٽڪ ايس اي پي ليبس زو
ڪيريو هاش هاشمي قائم ٿينديون

مسئلي جو بيان

"ڏنل عناصر جي سڀني قطار ۾ عام عنصر" مسئلو بيان ڪيو ويو آهي ته ، توهان کي 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 تائين پهچائينداسين. اهو ئي سبب آهي جڏهن اسان ميٽرڪس ۾ ٻي قطار جي لاءِ پيچرو ڪندا آهيون. ۽ جيڪڏھن اسان کي عنصر الف ۾ آھي نقشي ساڳيو ئي هڪ ٻئي قطار ۾ موجود آهي. مطلب ته اسان کي عام عنصر مليو آهي جيڪو هينئر تائين ٻن قطارن ۾ موجود آهي.

هاڻي قطار کي ٻئي قطار کان شروع ڪرڻ شروع ڪريو ، اسان چڪاس ڪنداسين ته هر قطار جو هر عنصر نقشي ۾ موجود آهي ، جيڪڏهن نقشي ۾ موجود آهي ته پوءِ انهي جو مطلب آهيnd هڪ عنصر کي صف ۾ بي عيب قطار ۾ ٻئين قطار ۾. اسان چڪاس ڪنداسين ته جيڪڏهن هر عنصر تعدد اسان کي چونڊيو موجوده قطار جي برابر آهي. اسان ان عنصر جي فريڪونسي جي قيمت کي اپڊيٽ ڪنداسين ۽ نقشي ۾ 1 وڌايو وڃي. تنهنڪري هر هڪ ٽرورسال لاءِ ، اسان انهي جي فريڪوئنسي کي جانچيندا سين جيڪڏهن اها قطار جي برابر آهي مطلب ته اهو مسلسل سمورن قطارن ۾ موجود آهي ، پوءِ اسان جڏهن چوٿين صف ۾ پهتل آهيون ته اسان ميٽرڪس جي انهن سڀني قدرن کي پرنٽ ڪري رهيا آهيون.

عام عناصر ڏنل ڏنل ميٽرڪس جي سڀني قطارن ۾

ڪوڊ

ڏنل ميٽرڪس جي سڀني قطار ۾ عام عنصر ڳولڻ لاءِ سي ++ ڪوڊ

#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

 

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (ايم * ن) جتي "م" ۽ “ن” ميٽرڪس ۾ قطار ۽ ڪالمن جو تعداد آهي. جئين اسان هش ايمپ استعمال ڪريون ٿا اسين او (1) وقت جي پيچيدگي ۾ داخل ڪرڻ ۽ ٻيا آپريشن ڪري سگهون ٿا. اھڙي طرح اھو (اين * ايم) ٽائيم پيچيدگي ۾ هلائڻ لاءِ الگورتھم ٺاھيو.

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

اي (ايم * ن) جتي "م" ۽ “ن” ميٽرڪس ۾ قطار ۽ ڪالمن جو تعداد آهي. جيئن ته ابتدائي ان پٽ خود سائز N * M جي آهي ، اسان اهو چئو ٿا خلائي پيچيدگي O (N * M) آهي.