දී ඇති පේළියක සියලුම අවසර ලත් පේළි සොයා ගන්න  


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ 24 * 7 නවෝත්පාදන විද්‍යාගාර ඇක්සෙන්චර් Expedia IBM ආයතනය ජේපී මෝගන් කෝරා
අරා හැෂ් හැෂිං නියමයන්

ගැටළු ප්රකාශය  

ලබා දී ඇති පේළියක සියලුම අවසර ලත් පේළි සොයා ගන්න, ඔබට m * 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 පමණක් තිබීම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.

 

පැහැදිලි කිරීම

ඔබට m m පේළි සහ n තීරු වල අනුකෘතියක් ලබා දී ඇති අතර පේළි අංකය, ලබා දී ඇති පේළි අංකය 0 දර්ශක පදනම් වේ. ලබා දී ඇති පේළිය හැර වෙනත් අනුකෘතියේ පේළි ලබා දී ඇති පේළියක ප්‍රේරණයන් දැයි සොයා බැලීමට අපි ඉල්ලා සිටිමු. මෙහි ප්‍රේරණය යනු ලබා දී ඇති මූලද්‍රව්‍යයන් දැයි අප සොයා ගත යුතු බවයි ලැයිස්තුව ලැයිස්තු ගණනක සමාන වේ, හෝ එකම ලැයිස්තු තිබීම හෝ නැත. අපි එම පේළි අංකය මුද්‍රණය කළ යුතුයි. මේ සඳහා අපි භාවිතා කිරීමට යන්නේ කට්ටලයක්.

මෙයද බලන්න
A + b + c = d වැනි විශාලතම d අරාවෙහි සොයා ගන්න

පළමුව, අපට දී ඇති පේළි අංකයේ සියලු අගයන් කට්ටලයට ඇතුළත් කළ යුතුය. මෙය අපගේ පසුකාලීන මෙහෙයුම් වලදී යොමු කිරීමක් ලෙස සලකනු ලැබේ. අපි මෙම පේළිය කට්ටලයට ගබඩා කර ඇත. මොකද අපි මේක තමයි හැර අනෙක් සියලුම පේළි සමඟ සංසන්දනය කරන්න යන්නේ.

කැදැලි ලූපයේ ආධාරයෙන් දැන් අනුකෘතිය හරහා ගමන් කරන්න. අපි සෑම පේළියක්ම තෝරා ගන්නා අතර එම පේළිය සමඟ අපි එහි සියලු අංග හරහා ගමන් කරන්නෙමු. අප විසින් ගනු ලබන පේළිය දී ඇති පේළියට සමාන නම් අපි නඩුවක් සඳහන් කර ඇත්තෙමු. ඉන්පසු එය නොසලකා ඊළඟ පේළිය තිබේ නම් ඉදිරියට යන්න. මෙයට හේතුව අප පිළිතුරට තවත් වටිනාකමක් එක් නොකිරීමයි. තවද එය පේළියේ තවත් එක් පේළියක් වැඩිපුර පෙන්වයි. එය පිළිගත නොහැකිය. දැන් අපි තෝරාගත් පේළියේ මූලද්රව්ය හරහා ගමන් කරන විට, අපි තෝරා ගන්නා විට කට්ටලය තුළ මූලද්රව්යය අඩංගු දැයි අපි පරීක්ෂා කරමු. ලූපය කිසිසේත් කැඩී නොයන්නේ නම්, මෙයින් අදහස් කරන්නේ, දී ඇති පේළිය ප්‍රේරණය වී ඇති අතර අපි එම පේළි අංකය මුද්‍රණය කිරීමට යන්නෙමු. තවත් පේළි ප්‍රේරණය වී තිබේද නැද්ද යන්න සොයා ගැනීමට තවදුරටත් ඉදිරියට යන්න.

දී ඇති පේළියක සියලුම අවසර ලත් පේළි සොයා ගන්නපින්

කේතය  

අනුකෘතියක දී දී ඇති පේළියක සියලුම අවසර ලත් පේළි සොයා ගැනීමට 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,

 

මෙයද බලන්න
වත්මන් අංක ලීට්කෝඩ් විසඳුමට වඩා සංඛ්‍යා කීයක් කුඩාද?

සංකීර්ණ විශ්ලේෂණය  

කාල සංකීර්ණත්වය

ඕ (එම් * එන්) එහිදී "එම්" සහ “N” යනු අනුකෘතියේ පේළි සහ තීරු ගණන වේ. අප හුදෙක් අනුකෘතිය හරහා ගමන් කරන නිසා සහ හැෂ්සෙට් නඩු පැවරීම O (1) හි මෙහෙයුම් සිදු කිරීමට සපයයි.

අභ්‍යවකාශ සංකීර්ණතාව

මත) එහිදී “එන්” යනු අනුකෘතියේ මූලද්‍රව්‍ය ගණන වේ. අපි දැන් ආදානය ගබඩා කර ඇති බැවින් ඇල්ගොරිතමයට රේඛීය අවකාශ සංකීර්ණතාවයක් ඇත.