Κοινά στοιχεία σε όλες τις σειρές ενός δεδομένου πίνακα


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις αμαζόνα Cisco DE Shaw Opera SAP Labs Zoho
Παράταξη Χασίσι Hashing Μήτρα

Δήλωση προβλήματος

Το πρόβλημα "Κοινά στοιχεία σε όλες τις σειρές ενός δεδομένου πίνακα" δηλώνει ότι, σας δίνεται ένας πίνακας 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. Αυτό συμβαίνει επειδή όταν διασχίζουμε τη δεύτερη σειρά σε έναν πίνακα. Και αν έχουμε το στοιχείο σε ένα χάρτη το ίδιο με το παρόν σε μια δεύτερη σειρά. Αυτό σημαίνει ότι βρήκαμε το κοινό στοιχείο προς το παρόν το οποίο υπάρχει μόνο σε δύο σειρές προς το παρόν.

Ξεκινήστε να διασχίζετε τη μήτρα τώρα από τη δεύτερη σειρά, θα ελέγξουμε εάν κάθε στοιχείο κάθε σειράς υπάρχει στον χάρτη, εάν υπάρχει στον χάρτη, αυτό σημαίνει ότι αυτό είναι το 2nd εμφάνιση αυτού του στοιχείου σε έναν πίνακα διαδοχικά σε μια δεύτερη σειρά. Θα ελέγξουμε εάν κάθε συχνότητα στοιχείων που επιλέξαμε είναι ίση με την τρέχουσα σειρά. Θα ενημερώσουμε την τιμή της συχνότητας αυτού του στοιχείου και θα την αυξήσουμε κατά 1 στο χάρτη. Έτσι, για κάθε διασταύρωση, θα ελέγξουμε τη συχνότητά του εάν είναι ίση με την πρώτη σειρά που σημαίνει ότι υπάρχει διαδοχικά σε όλες τις σειρές, και τότε θα εκτυπώνουμε όλες αυτές τις τιμές ενός πίνακα όταν βρισκόμαστε στην τελευταία γραμμή.

Κοινά στοιχεία σε όλες τις σειρές ενός δεδομένου πίνακα

Κώδικας

C ++ Code για να βρείτε κοινά στοιχεία σε όλες τις σειρές ενός δεδομένου πίνακα

#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

Κωδικός Java για την εύρεση κοινών στοιχείων σε όλες τις σειρές ενός δεδομένου πίνακα

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) όπου "M"   «Ν» είναι ο αριθμός γραμμών και στηλών στη μήτρα. Δεδομένου ότι χρησιμοποιούμε το HashMap μπορούμε να κάνουμε εισαγωγή και άλλες λειτουργίες σε χρονική πολυπλοκότητα O (1) Έτσι, αυτό δημιουργεί έναν αλγόριθμο για να τρέξει σε O (N * M) πολυπλοκότητα χρόνου.

Διαστημική πολυπλοκότητα

O (m * n) όπου "M"   «Ν» είναι ο αριθμός γραμμών και στηλών στη μήτρα. Δεδομένου ότι η ίδια η αρχική είσοδος έχει μέγεθος N * M, λέμε ότι η πολυπλοκότητα του διαστήματος είναι O (N * M).