ค้นหาองค์ประกอบที่แตกต่างกันทั่วไปสำหรับทุกแถวของเมทริกซ์


ระดับความยาก ยาก
ถามบ่อยใน แบล็ค Expedia มอร์แกน JP วอลคอมม์ Snapdeal Yatra Zoho
hashing มดลูก การเรียงลำดับ

คำชี้แจงปัญหา

เราได้รับเมทริกซ์ของจำนวนเต็มทั้งหมด ปัญหา“ ค้นหาองค์ประกอบที่แตกต่างที่พบบ่อยในทุกแถวของเมทริกซ์” ขอให้ค้นหาองค์ประกอบที่แตกต่างกันทั้งหมดที่เป็นไปได้ แต่พบได้บ่อยในแต่ละแถวที่มีอยู่ในเมทริกซ์

ตัวอย่าง

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.

คำอธิบาย

กำหนดเมทริกซ์ของจำนวนเต็ม งานของเราคือค้นหาค่าที่เป็นไปได้ทั้งหมดของเมทริกซ์ที่แตกต่างกัน และทั่วไปในแต่ละแถวในเมทริกซ์ เราจะใช้โครงสร้างข้อมูลชุดในการแก้ปัญหานี้ โครงสร้างข้อมูลชุดนี้ช่วยในการลบหรือไม่ยอมรับองค์ประกอบที่คัดลอก เราจะข้ามเมทริกซ์จากแถวที่สองของเมทริกซ์ เพราะแถวแรกเราจะกำหนดให้เป็น Set อยู่แล้ว

เราจะประกาศชุดแรกที่เรียกว่า SETValue และเพิ่มค่าทั้งหมดของแถวแรกของเมทริกซ์ลงในชุด นี่เป็นเพียงเพราะเราต้องตรวจสอบองค์ประกอบทั้งหมดที่ควรจะเป็นเหมือนกันในทุกแถว ดังนั้นเราจึงสามารถใช้แถวแรกที่จะกำหนดให้กับ Set เป็นข้อมูลอ้างอิงได้

ตอนนี้เราจะข้ามเมทริกซ์จากองค์ประกอบแถวที่สองเพราะเราได้ครอบคลุมแถวแรกแล้วและจากแถวที่สองเราจะทำการใหม่ ชุด ในความเป็นจริงโครงสร้างข้อมูลเราจะใช้โครงสร้างข้อมูลใหม่สำหรับแต่ละแถวใหม่ของเมทริกซ์ที่กำหนดในการส่งผ่าน เนื่องจากเราต้องจัดเก็บองค์ประกอบแถวเฉพาะเหล่านั้นไว้ใน Set ใหม่ที่เรียกว่า "temp" จากนั้นเราจะตรวจสอบว่ามีค่าของ SETValue อยู่ใน temp หรือไม่ถ้ามีเราจะลบองค์ประกอบนั้นออก นอกจากนี้เราได้ใส่เงื่อนไขหนึ่งไว้ที่นั่นเพื่อตรวจสอบค่าข้อยกเว้นของพอยน์เตอร์ว่าง หากขนาดของชุด SETValue กลายเป็น 0 มันจะทำลายลูปและจะไม่มีข้อผิดพลาดรันไทม์

ในขณะที่เรากำลังลบองค์ประกอบออกจาก SETValue เราจะมีค่าเอาต์พุตอยู่ในนั้นหลังจากการส่งผ่านดังนั้นเราจะพิมพ์ค่าเหล่านั้น

ค้นหาองค์ประกอบที่แตกต่างกันทั่วไปสำหรับทุกแถวของเมทริกซ์

รหัส

รหัส 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

โค้ด Java เพื่อค้นหาองค์ประกอบที่แตกต่างกันทั่วไปสำหรับทุกแถวของเมทริกซ์

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

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

ที่นี่เราใช้สองลูปซ้อนกันและการใช้ unordered_set / HashSet ทำให้เรามีความซับซ้อนของเวลาพหุนาม บน2) ที่ไหน “ n” คือขนาดของเมทริกซ์

ความซับซ้อนของอวกาศ

O (n) ที่ไหน “ n” คือขนาดของเมทริกซ์สำหรับจัดเก็บอินพุตและจัดเก็บองค์ประกอบใน HashSet