ھڪڙي ميٽرڪس جي سڀني قطار ڏانھن عام عناصر ڳوليو


تڪليف جي سطح سخت
بار بار پڇڻ ۾ ڪاروڪ Expedia JP مارگن Qualcomm اسپيڊل ياترا زو
هاشمي قائم ٿينديون ترتيب ڏيڻ

مسئلي جو بيان

اسان کي سڀني انٽيگرز جي هڪ ميٽرڪس ڏني وئي آهي. مسئلو “ميٽرڪس جي سڀني قطارن لاءِ عام عناصر ڳوليو” سڀني ممڪن عنصرن کي ڳولڻ جي لاءِ عرض ڪيو پر هر هڪ قطار ۾ عام آهي.

مثال

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.

وضاحت

انٽيگرز جي هڪ ميٽرڪس ڏني. اسان جو ڪم اهو آهي ته ميٽرڪس جي سڀني ممڪن قدرن کي ڳولڻ گهرجي جيڪي هڪ ٻئي لاءِ ڌار آهن. ۽ ميٽرڪس ۾ هر قطار ۾ پڻ عام آهي. اسان انهي سوال کي حل ڪرڻ ۾ سيٽ ڊيٽا اسٽرڪچر استعمال ڪنداسين. انهي ڊيٽا جي جوڙجڪ کي ڪاپي ٿيل عنصر کي ختم ڪرڻ يا قبول نه ڪرڻ ۾ مدد ملندي آهي. اسان ميٽرڪس جي ٻئي قطار کان ميٽرڪس مان گذري سگهنداسين. ڇاڪاڻ ته پهرين قطار اسان کي هڪ سيٽ تي اڳي ئي تفويض ٿيندي.

اسان هڪ سيٽ کي پهريون اعلان ڪنداسين SETValue ۽ هڪ ميٽرڪس جي پهرين صف جي سڀني قدرن کي سيٽ ۾ شامل ڪنداسين. اهو صرف ان لاءِ آهي ته اسان کي انهن سڀني عنصرن کي چيڪ ڪرڻو آهي جيڪي انهن سڀني صفن ۾ عام هجن. تنهن ڪري اسان پهرين قطار کي استعمال ڪري سگهون ٿا جيڪي هڪ سيٽ کي حوالي جي طور تي تفويض ڪيا ويندا.

اسان ميٽرڪس مان هاڻي ٻئي قطار واري عنصرن مان نڪري وينداسين ڇاڪاڻ ته اسان پهرين قطار کي haveڪي چڪا آهيون ۽ هاڻي ٻئي قطار کان اسان نئين ورتو ويندو. مقرر ڊيٽا جو structureانچو ، حقيقت ۾ ، اسان ٽرورسال ۾ ڏنل ميٽرڪس جي هر نئين قطار لاءِ نئين ڊيٽا اسٽرڪچر وٺي رهيا هوندا. ڇو ته اسان کي انهن مخصوص قطار عنصرن کي ”ٽمپ“ سڏيو ويندو آهي. ته پوءِ اسان جاچ ڪرڻ وارا آهيون جيڪڏهن SETValue جي ڪا قيمت ٽائيم ۾ موجود آهي جيڪڏهن موجود آهي ته پوءِ انهي عنصر کي ختم ڪرڻ وارا آهيون. انهي کان علاوه ، اسان هڪ شرط رکيا آهيون نيل پوائنٽر جي استثنا واري قيمت کي جانچڻ لاءِ. جيڪڏهن سيٽل ويليوٽ سيٽ جو سائز 0 ٿي ويندو ته اھو لوپ کي ٽوڙيندو ۽ رن ٽائيم خرابي ناھي.

جئين اسان SETValue کان عنصرن کي ڪ areي رهيا آهيون ، اسان وٽ طويل طريقي کان پوءِ اسان جي پيداوار ويليو آهي ، تنهنڪري اسان انهن قدرن کي پرنٽ ڪري رهيا آهيون.

ھڪڙي ميٽرڪس جي سڀني قطار ڏانھن عام عناصر ڳوليو

ڪوڊ

هڪ ميٽرڪس جي سڀني قطارن لاءِ عام عناصر ڳولڻ لاءِ 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

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

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

هتي اسان ٻه استعمال ٿيل لوپ استعمال ڪيا ويا آهيون ۽ غير ترتيب ٿيل_سٽ / هش سيٽ کي استعمال ڪندي اسان کي پولينيومل ٽائيم پيچيدگي ڏني. اي (اين2) جتي “ن” ميٽرڪس جي ماپ آهي.

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

اي (ن) جتي “ن” سائيز جي ماپ آهي ، داخل ڪرڻ ۽ عناصر کي محفوظ ڪرڻ جي هش سيٽ ۾.