ম্যাট্রিক্সের সমস্ত সারিতে পৃথক উপাদানগুলি সন্ধান করুন


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় কালো শিলা এক্সপিডিয়া জেপি মরগান কোয়ালকম Snapdeal রথযাত্রা 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.

ব্যাখ্যা

পূর্ণসংখ্যার একটি ম্যাট্রিক্স দেওয়া হয়েছে। আমাদের কাজ হ'ল ম্যাট্রিক্সের সমস্ত সম্ভাব্য মান যা একে অপরের সাথে স্বতন্ত্র find এবং ম্যাট্রিক্সের প্রতিটি সারিতেও সাধারণ। আমরা এই প্রশ্নটি সমাধান করতে ডেটা স্ট্রাকচার ব্যবহার করব। এই সেট ডেটা স্ট্রাকচার অনুলিপি করা উপাদানগুলি অপসারণ বা না গ্রহণে সহায়তা করে। আমরা ম্যাট্রিক্সের দ্বিতীয় সারি থেকে ম্যাট্রিক্সকে অনুসরণ করব। কারণ প্রথম সারিতে আমরা ইতিমধ্যে একটি সেট বরাদ্দ করা হবে।

আমরা প্রথমে SETValue নামক একটি সেট ঘোষণা করব এবং একটি ম্যাট্রিক্সের প্রথম সারির সমস্ত মান সেটগুলিতে যুক্ত করব। এটি কেবল কারণ আমাদের সমস্ত উপাদানগুলিকে পরীক্ষা করতে হবে যা সমস্ত সারিতে সাধারণ হওয়া উচিত। সুতরাং আমরা প্রথম সারিটি ব্যবহার করতে পারি যা রেফারেন্স হিসাবে একটি সেটকে বরাদ্দ করা হবে।

আমরা এখন দ্বিতীয় সারির উপাদানগুলি থেকে ম্যাট্রিক্সের সন্ধান করব কারণ আমরা ইতিমধ্যে প্রথম সারিটি coveredেকে রেখেছি এবং এখন দ্বিতীয় সারি থেকে আমরা একটি নতুন গ্রহণ করব সেট তথ্য কাঠামো, প্রকৃতপক্ষে, আমরা ট্র্যাভারসালটিতে প্রদত্ত ম্যাট্রিক্সের প্রতিটি নতুন সারির জন্য নতুন ডেটা স্ট্রাকচার গ্রহণ করব। কারণ আমাদের সেই নির্দিষ্ট সারির উপাদানগুলিকে "টেম্প" নামক নতুন সেটে সংরক্ষণ করতে হবে। তারপরে আমরা যাচাই করতে যাচ্ছি যে এসটিটিভ্যালুটির কোনও মান যদি টেম্পে উপস্থিত থাকে তবে উপস্থিত থাকলে আমরা সেই উপাদানটি সরাতে যাচ্ছি। এছাড়াও, আমরা নাল পয়েন্টার ব্যতিক্রম মান পরীক্ষা করতে সেখানে একটি শর্ত রেখেছি। যদি SETValue সেটটির আকার 0 হয়ে যায়, তবে এটি লুপটি ভেঙে দেবে এবং কোনও রানটাইম ত্রুটি হবে না।

যেহেতু আমরা SETValue থেকে উপাদানগুলি সরিয়ে দিচ্ছি, ট্র্যাভারসাল করার পরে আমাদের সেখানে একটি আউটপুট মান রয়েছে, সুতরাং আমরা সেই মানগুলি মুদ্রণ করব।

ম্যাট্রিক্সের সমস্ত সারিতে পৃথক উপাদানগুলি সন্ধান করুন

কোড

ম্যাট্রিক্সের সমস্ত সারিতে আলাদা আলাদা উপাদানগুলি খুঁজে পেতে সি ++ কোড

#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) কোথায় "এন" ম্যাট্রিক্সের আকার।

স্পেস জটিলতা ity

উপর) কোথায় "এন" হ্যাশসেটে ইনপুট এবং উপাদান সংরক্ষণের জন্য ম্যাট্রিক্সের আকার।