Берилген матрицанын бардык катарларындагы жалпы элементтер


Кыйынчылык деңгээли орто
Көп суралган Amazon Cisco DE Shaw опера SAP Labs Zoho
согуштук тизме таштанды Hashing Matrix

Маселени билдирүү

"Берилген матрицанын бардык катарларындагы жалпы элементтер" маселеси, сизге 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ге чейин баштайбыз, себеби матрицанын экинчи катарынан өткөндө. Эгерде бизде а карта экинчи катарда болгондой эле. Демек, азырынча эки катардан турган жалпы элементти таптык.

Эми экинчи саптан баштап матрицаны кыдырып баштаңыз, ар бир катардын ар бир элементинин картада бар-жогун текшерип, эгер ал картада бар болсо, демек бул 2 дегенди билдиретnd ошол элементтин экинчи катарда катары менен матрицада пайда болушу. Тандалган ар бир элементтин жыштыгы учурдагы сапка барабар экендигин текшерип жатабыз. Биз ошол элементтин жыштыгынын маанисин жаңыртып, картада 1ге көбөйтөбүз. Ошентип, ар бир өтүү үчүн, биз анын жыштыгын текшеребиз, эгерде ал i'th катарына барабар болсо, анда ал бардык катарларда удаалаш болуп турат, ошондо биз матрицанын бардык баалуулуктарын акыркы катар өтүүдө болгондо басып чыгарабыз.

Берилген матрицанын бардык катарларындагы жалпы элементтер

коду

Берилген матрицанын бардык катарларындагы жалпы элементтерди табуу үчүн C ++ коду

#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) кайда "М" жана "N" матрицадагы катарлардын жана мамылардын саны. HashMap колдонулгандыктан, киргизүү жана башка операцияларды O (1) убакыт татаалдыгында жасай алабыз. Ошентип, бул O (N * M) убакыт татаалдыгында иштөө алгоритмин түзөт.

Космостун татаалдыгы

O (m * n) кайда "М" жана "N" матрицадагы катарлардын жана мамылардын саны. Баштапкы киргизүү өзү N * M өлчөмүндө болгондуктан, биз мейкиндиктин татаалдыгын O (N * M) дейбиз.