Bir matrisdə verilən bir cərgənin bütün əvəz olunmuş satırlarını tapın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur 24 * 7 İnnovasiya Laboratoriyaları Accenture Expedia IBM JP Morgan Quora
Geyim Sükut Hashing MatrisBaxılıb 41

Problem bəyanat

Bir matrisdəki verilmiş sətrin bütün permuted satırlarını tapın ki, sizə m * n ölçülü bir matris verilmişdir və matris sətir nömrəsi 'satır' deyir. Problem ifadəsi, verilmiş sətirə permütasiya olan bütün mümkün sətirləri tapmağı xahiş edir. Hər satırdakı bütün elementlərin fərqli olduğu da deyilir.

misal

r = 2

mat[][] = {{6, 5, 9, 2},

{1, 6, 9, 3},

{6, 5, 9, 2},

{6, 2, 5, 9}}
0, 3

İzahat: Verilən sətir 2, 6, 5 və 2-dan ibarət olan 9-dir. Bunun yalnız 0 olmasıth və 3rd sıra verilən sıra nömrəsinə permutasiyalardır.

 

Bir matrisdə verilmiş bir sətrin bütün əvəzlənmiş sətirlərini tapmaq üçün alqoritm

1. Create a set.
2. Insert the given row elements into the set.
3. Traverse the matrix, and ignore the given row number while traversing.
    1. Check if the set doesn’t contain each value of the traversed row if it doesn’t contain then break the loop and proceed for next row.
    2. Else print the value of i, i.e, the current row number.

 

Izahat

Sizə say m satır və n sütun matrisası və sətir nömrəsi verilir, verilən sətir nömrəsi 0 indeksə əsaslanır. Matrisdəki verilmiş sətirdən başqa satırların verilmiş sətrin permütasiyaları olub olmadığını öyrənməyimizi xahiş etdik. Buradakı icazə, verilən elementlərin olub olmadığını öyrənməliyik deməkdir siyahı neçə siyahıda eynidir, ya da eyni siyahılara sahibdir, ya yox. Həmin sıra nömrəsini çap etməliyik. Bunun üçün istifadə edəcəyik Set.

Əvvəlcə verilən sıra nömrəsinin bütün dəyərlərini dəstə daxil etməyimiz lazımdır. Bu, sonrakı əməliyyatlarımızda istinad kimi qəbul edilir. Bu cərgəni dəstdə saxladıq. Çünki bunu özündən başqa bütün satırlarla müqayisə edəcəyik.

İndi iç içə döngənin köməyi ilə matrisdən keçin. Hər satırı seçəcəyik və bu sıra ilə bütün elementlərini keçəcəyik. Yığacağımız sıra verilən sətirlə eyni olduqda bir iş qeyd etdik. Sonra buna məhəl qoymayın və varsa növbəti sıraya keçin. Bunun səbəbi, cavaba daha bir dəyər əlavə etməyəcəyik. Və satırın özü olan daha bir sıra əlavə göstərir. Bu məqbul olmazdı. İndi seçilmiş sətrin elementlərini keçdiyimiz zaman yığımda yığım elementinin olub olmadığını yoxlayırıq. Döngü ümumiyyətlə qırılmır və bu çıxırsa, verilən sıra əvəzlənir və biz həmin sıra nömrəsini çap edəcəyik. Daha çox satırın dəyişdirildiyini və ya olmadığını öyrənmək üçün daha da davam edin.

Bir matrisdə verilən bir cərgənin bütün əvəz olunmuş satırlarını tapınPin

Kodu

Bir matrisdə verilən bir satırın bütün permuted satırlarını tapmaq üçün C ++ kodu

#include<iostream>
#include<unordered_set>

#define MAX 100

using namespace std;

void checkPermutatedRow(int matrix[][MAX], int m, int n, int r)
{
    unordered_set<int> s;

    for (int j=0; j<n; j++)
        s.insert(matrix[r][j]);

    for (int i=0; i<m; i++)
    {
        if (i==r)
            continue;

        int j;
        for (j=0; j<n; j++)
            if (s.find(matrix[i][j]) == s.end())
                break;
        if (j != n)
            continue;

        cout << i << ", ";
    }
}
int main()
{
    int row = 4, col = 4,r = 2;
    int matrix[][MAX] = {{6, 5, 9, 2},
        {1, 6, 9, 3},
        {6, 5, 9, 2},
        {6, 2, 5, 9}
    };
    checkPermutatedRow(matrix, row, col, r);
    return 0;
}
0, 3,

Bir matrisdə verilən bir satırın bütün permuted satırlarını tapmaq üçün Java Kodu

import java.util.LinkedHashSet;

class Permutations
{
    private static int MAX = 100;

    public static void checkPermutatedRow(int matrix[][], int m, int n, int r)
    {
        LinkedHashSet<Integer> SET = new LinkedHashSet<>();

        for (int j = 0; j < n; j++)
            SET.add(matrix[r][j]);

        for (int i = 0; i < m; i++)
        {
            if (i == r)
                continue;

            int j;
            for (j = 0; j < n; j++)
                if (!SET.contains(matrix[i][j]))
                    break;
            if (j != n)
                continue;

            System.out.print(i+", ");
        }
    }
    public static void main(String[] args)
    {
        int  row= 4, col = 4,r = 2;
        int matrix[][] = {{6, 5, 9, 2},
            {1, 6, 9, 3},
            {6, 5, 9, 2},
            {6, 2, 5, 9}
        };
        checkPermutatedRow(matrix, row, col, r);
    }
}
0, 3,

 

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (m * n) hara "M" və "N" matritsadakı sətir və sütun sayıdır. Sadəcə matrisdən keçdiyimiz və HashSet-ə müraciət etdiyimiz üçün əməliyyatların O (1) -də aparılması təmin olunur.

Kosmik Mürəkkəblik

O (N) hara "N" matrisdəki elementlərin sayıdır. Girişi yeni saxladığımız üçün alqoritm xətti kosmik mürəkkəbliyə malikdir.

Translate »