我们得到一个由正整数和行号组成的m*n矩阵。任务是找到给定矩阵中的所有行，这些行是给定行元素的排列。还指出每一行中的值都是不同的。
null
例如：
Input : mat[][] = {{3, 1, 4, 2}, {1, 6, 9, 3}, {1, 2, 3, 4}, {4, 3, 2, 1}} row = 3 Output: 0, 2Rows at indexes 0 and 2 are permutations ofrow at index 3.
A. 简单解决方案 是对所有行逐个排序并检查所有行。如果任何一行完全等于给定的行，这意味着当前行是给定行的排列。这个 时间复杂性 对于这种方法，将是O（m*n logn）。
一 有效的方法 就是使用散列。只需创建一个 Hash集 对于给定的行。创建哈希集后，遍历剩余的行，并针对每一行检查哈希集中是否存在其所有元素。
CPP
// C++ program to find all permutations of a given row #include<bits/stdc++.h> #define MAX 100 using namespace std; // Function to find all permuted rows of a given row r void permutatedRows( int mat[][MAX], int m, int n, int r) { // Creating an empty set unordered_set< int > s; // Count frequencies of elements in given row r for ( int j=0; j<n; j++) s.insert(mat[r][j]); // Traverse through all remaining rows for ( int i=0; i<m; i++) { // we do not need to check for given row r if (i==r) continue ; // initialize hash i.e; count frequencies // of elements in row i int j; for (j=0; j<n; j++) if (s.find(mat[i][j]) == s.end()) break ; if (j != n) continue ; cout << i << ", " ; } } // Driver program to run the case int main() { int m = 4, n = 4,r = 3; int mat[][MAX] = {{3, 1, 4, 2}, {1, 6, 9, 3}, {1, 2, 3, 4}, {4, 3, 2, 1}}; permutatedRows(mat, m, n, r); return 0; } |
JAVA
// Java program to find all permutations of a given row import java.util.*; class GFG { static int MAX = 100 ; // Function to find all permuted rows of a given row r static void permutatedRows( int mat[][], int m, int n, int r) { // Creating an empty set LinkedHashSet<Integer> s = new LinkedHashSet<>(); // Count frequencies of elements in given row r for ( int j = 0 ; j < n; j++) s.add(mat[r][j]); // Traverse through all remaining rows for ( int i = 0 ; i < m; i++) { // we do not need to check for given row r if (i == r) continue ; // initialize hash i.e; count frequencies // of elements in row i int j; for (j = 0 ; j < n; j++) if (!s.contains(mat[i][j])) break ; if (j != n) continue ; System.out.print(i+ ", " ); } } // Driver program to run the case public static void main(String[] args) { int m = 4 , n = 4 ,r = 3 ; int mat[][] = {{ 3 , 1 , 4 , 2 }, { 1 , 6 , 9 , 3 }, { 1 , 2 , 3 , 4 }, { 4 , 3 , 2 , 1 }}; permutatedRows(mat, m, n, r); } } // This code has been contributed by 29AjayKumar |
Python3
# Python program to find all # permutations of a given row # Function to find all # permuted rows of a given row r def permutatedRows(mat, m, n, r): # Creating an empty set s = set () # Count frequencies of # elements in given row r for j in range (n): s.add(mat[r][j]) # Traverse through all remaining rows for i in range (m): # we do not need to check # for given row r if i = = r: continue # initialize hash i.e # count frequencies # of elements in row i for j in range (n): if mat[i][j] not in s: # to avoid the case when last # element does not match j = j - 2 break ; if j + 1 ! = n: continue print (i) # Driver program to run the case m = 4 n = 4 r = 3 mat = [[ 3 , 1 , 4 , 2 ], [ 1 , 6 , 9 , 3 ], [ 1 , 2 , 3 , 4 ], [ 4 , 3 , 2 , 1 ]] permutatedRows(mat, m, n, r) # This code is contributed # by Upendra Singh Bartwal. |
C#
// C# program to find all permutations of a given row using System; using System.Collections.Generic; class GFG { static int MAX = 100; // Function to find all permuted rows of a given row r static void permutatedRows( int [,]mat, int m, int n, int r) { // Creating an empty set HashSet< int > s = new HashSet< int >(); // Count frequencies of elements in given row r for ( int j = 0; j < n; j++) s.Add(mat[r, j]); // Traverse through all remaining rows for ( int i = 0; i < m; i++) { // we do not need to check for given row r if (i == r) continue ; // initialize hash i.e; count frequencies // of elements in row i int j; for (j = 0; j < n; j++) if (!s.Contains(mat[i,j])) break ; if (j != n) continue ; Console.Write(i+ ", " ); } } // Driver program to run the case public static void Main(String[] args) { int m = 4, n = 4,r = 3; int [,]mat = {{3, 1, 4, 2}, {1, 6, 9, 3}, {1, 2, 3, 4}, {4, 3, 2, 1}}; permutatedRows(mat, m, n, r); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript program to find all permutations of a given row let MAX = 100; // Function to find all permuted rows of a given row r function permutatedRows(mat, m, n, r) { // Creating an empty set let s = new Set(); // Count frequencies of elements in given row r for (let j = 0; j < n; j++) s.add(mat[r][j]); // Traverse through all remaining rows for (let i = 0; i < m; i++) { // we do not need to check for given row r if (i == r) continue ; // initialize hash i.e; count frequencies // of elements in row i let j; for (j = 0; j < n; j++) if (!s.has(mat[i][j])) break ; if (j != n) continue ; document.write(i+ ", " ); } } // Driver program let m = 4, n = 4,r = 3; let mat = [[ 3, 1, 4, 2], [1, 6, 9, 3], [1, 2, 3, 4], [4, 3, 2, 1]]; permutatedRows(mat, m, n, r); </script> |
输出：
0, 2
时间复杂性： O（m*n） 辅助空间： O（n）
解决方案的另一种方法是使用标准模板库（STL）：
CPP
// C++ program to find all permutations of a given row #include<bits/stdc++.h> #define MAX 100 using namespace std; // Function to find all permuted rows of a given row r void permutatedRows( int mat[][MAX], int m, int n, int r) { for ( int i=0; i<m&&i!=r; i++){ if (is_permutation(mat[i],mat[i]+n,mat[r])) cout<<i<< "," ; } } // Driver program to run the case int main() { int m = 4, n = 4,r = 3; int mat[][MAX] = {{3, 1, 4, 2}, {1, 6, 9, 3}, {1, 2, 3, 4}, {4, 3, 2, 1}}; permutatedRows(mat, m, n, r); return 0; } |
输出：
0, 2
练习： 将上述解决方案扩展到一个输入矩阵，其中一行的所有元素都不必是不同的。（点击：我们可以使用 哈希映射 而不是散列集） 本文由 沙申克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
