በአንድ ማትሪክስ ውስጥ የተሰጠው ረድፍ ሁሉንም የተጠለፉ ረድፎችን ያግኙ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ 24 * 7 የፈጠራ ላብራቶሪዎች Accenture Expedia IBM ጂፒ ሞርጋን Quora
ሰልፍ ሃሽ ሃምሽንግ ማትሪክስ

የችግሩ መግለጫ

በአንድ ማትሪክስ ውስጥ የተሰጡትን ረድፎች ሁሉ የተጠለፉ ረድፎችን ያግኙ መጠን * * n ማትሪክስ እንደተሰጠዎት እና የማትሪክስ ረድፍ ቁጥር ‹ረድፍ› ይላል ፡፡ የችግሩ መግለጫ በተሰጠው ረድፍ ላይ ጥልፍተኛ ሊሆኑ የሚችሉትን ሁሉንም ረድፎች ለመፈለግ ይጠይቃል ፡፡ ይህ በተጨማሪም በእያንዳንዱ ረድፍ ውስጥ ያሉት ሁሉም ንጥረ ነገሮች የተለያዩ ናቸው ተብሏል ፡፡

ለምሳሌ

r = 2

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

{1, 6, 9, 3},

{6, 5, 9, 2},

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

ማብራሪያ-የተሰጠው ረድፍ 2 ​​ነው 6 ፣ 5 ፣ 2 እና 9 የያዘ 0. ይህንን ብቻ XNUMX ያለውth እና 3rd ረድፍ በተሰጠው ረድፍ ቁጥር ላይ ጥፋቶች ናቸው ፡፡

 

በአንድ ማትሪክስ ውስጥ የተሰጠው ረድፍ ሁሉንም የተጎዱ ረድፎችን ለማግኘት አልጎሪዝም

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.

 

ማስረጃ

የ ‹ሜ ረድፎች› እና የ ‹አምዶች› እና የረድፍ ቁጥር ማትሪክስ ተሰጥቶዎታል ፣ የተሰጠው ረድፍ ቁጥር በ 0 መረጃ ጠቋሚ ላይ የተመሠረተ ነው ፡፡ ከተሰጠው ረድፍ ውጭ በማትሪክስ ውስጥ ያሉት ረድፎች የአንድ ረድፍ ጥሰቶች መሆናቸውን ለማወቅ ጠይቀናል ፡፡ እዚህ መቦርቦር ማለት በተሰጠው ውስጥ ያሉት ንጥረ ነገሮች ካሉ ማወቅ አለብን ማለት ነው ዝርዝር ምን ያህል ዝርዝሮች ተመሳሳይ ናቸው ፣ ወይም ተመሳሳይ ዝርዝር ያላቸው ወይም የሌሉ ናቸው። ያንን የረድፍ ቁጥር ማተም ያስፈልገናል። ለዚህም እኛ ልንጠቀምበት ነው አዘጋጅ.

በመጀመሪያ ፣ የተሰጠው የረድፍ ቁጥር ሁሉንም እሴቶች ወደ ስብስቡ ውስጥ ማስገባት ያስፈልገናል። ይህ በኋለኞቹ ሥራዎቻችን እንደ ማጣቀሻ ተደርጎ ይወሰዳል ፡፡ ይህንን ረድፍ ወደ ስብስቡ ውስጥ አስቀምጠናል ፡፡ ምክንያቱም ይህንን ከራሱ በስተቀር ከሌሎቹ ሁሉም ረድፎች ጋር እናወዳድረዋለን ፡፡

በተሸፈነው ሉፕ በመታገዝ አሁኑኑ ማትሪክስን ያቋርጡ ፡፡ እያንዳንዱን ረድፍ እንመርጣለን እና በዛ ረድፍ ሁሉንም ንጥረ ነገሮችን እናልፋለን ፡፡ የምንወስደው ረድፍ ከተሰጠው ረድፍ ጋር ተመሳሳይ ከሆነ አንድ ጉዳይ ጠቅሰናል ፡፡ ከዚያ ችላ ይበሉ እና ካለ ለሚቀጥለው ረድፍ ያንቀሳቅሱ። ይህ የሆነበት ምክንያት በመልሱ ላይ አንድ ተጨማሪ እሴት ስላልጨመርን ነው ፡፡ እና እሱ ራሱ አንድ ረድፍ ተጨማሪ ያሳያል ይህም ራሱ ረድፍ ነው። ያ ተቀባይነት የለውም ፡፡ አሁን የተመረጠውን ረድፍ አካላት በምንሻገርበት ጊዜ እኛ በምንወስድበት ጊዜ ስብስቡ የተቀመጠውን ንጥረ ነገር የያዘ መሆኑን እናረጋግጣለን ፡፡ ቀለበቱ ጨርሶ የማይሰበር ከሆነ እና ይህ ማለት የሚወጣው ከሆነ የተሰጠው ረድፍ ተደምጧል እናም ያንን የረድፍ ቁጥር እናተምበታለን ፡፡ ተጨማሪ ረድፎች የተጠለፉ ወይም እንዳልሆኑ ለማወቅ የበለጠ ይቀጥሉ።

በአንድ ማትሪክስ ውስጥ የተሰጠው ረድፍ ሁሉንም የተጠለፉ ረድፎችን ያግኙ

ኮድ

በአንድ ማትሪክስ ውስጥ የተሰጠው ረድፍ ሁሉንም የተጎዱ ረድፎችን ለማግኘት የ C ++ ኮድ

#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,

የጃቫ ኮድ በማትሪክስ ውስጥ የተሰጠው ረድፍ ሁሉንም የተጠለፉ ረድፎችን ለማግኘት

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 * n) የት "M" ና “N” በማትሪክስ ውስጥ የረድፎች እና አምዶች ብዛት ነው። እኛ በቀላሉ ማትሪክሱን እየተሻገርን እና በ ‹ኦ› (1) ውስጥ ክዋኔዎችን ለማከናወን በ HashSet ክስ የምንመሰርት ስለሆነ ፡፡

የቦታ ውስብስብነት

ኦ (ኤን) የት "N" በማትሪክስ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። እኛ ግቤቱን አሁን ስላከማንነው ፣ ስለሆነም አልጎሪዝም መስመራዊ የቦታ ውስብስብነት አለው።