查找矩陣中給定行的所有置換行


難度級別
經常問 24 * 7創新實驗室 埃森哲 Expedia的 IBM JP摩根 Quora的
排列 哈希 哈希 矩陣

問題陳述

在矩陣中找到給定行的所有排列後的行,表示給定的是大小為m * n的矩陣,並且矩陣行號為'row'。 問題陳述要求找出與給定行排列的所有可能的行。 也可以說每一行中的所有元素都是不同的。

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。只有0th 和3rd row是給定行號的排列。

 

查找矩陣中給定行的所有置換行的算法

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行和n列以及行號,給出的行號基於0索引。 我們要求找出矩陣中除給定行之外的其他行是否是給定行的排列。 這裡的排列意味著我們必須找出給定元素是否 在多少個列表中是相同的,或者是否具有相同的列表。 我們需要打印該行號。 為此,我們將使用 在你的生活中.

首先,我們需要將給定行號的所有值插入到集合中。 在以後的操作中將其作為參考。 我們已將此行存儲到集合中。 因為我們將把它與除自身以外的所有其他行進行比較。

現在藉助嵌套循環遍歷矩陣。 我們將選擇每一行,並在該行中遍歷其所有元素。 我們已經提到了一種情況,如果我們要拾取的行與給定的行相同。 然後忽略它,並移動到下一行(如果存在)。 這是因為我們不會在答案中再增加一個價值。 它顯示了另外一行,這本身就是行。 那是不可接受的。 現在,當我們遍歷拾取行的元素時,我們將在拾取時檢查集合中是否包含set元素。 如果循環根本沒有中斷並出現,這意味著給定的行將被置換,我們將打印該行號。 進一步查找更多是否被置換的行。

查找矩陣中給定行的所有置換行

推薦碼

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,

Java代碼查找矩陣中給定行的所有置換行

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,

 

複雜度分析

時間複雜度

O(米* n) 哪裡 “m”個 或 “ n” 是矩陣中的行數和列數。 由於我們只是遍歷矩陣並使用HashSet來執行O(1)中的操作。

空間複雜度

上) 哪裡 “ N” 是矩陣中元素的數量。 由於我們只是存儲輸入,因此該算法具有線性空間複雜度。