给定一个nxn矩阵，其中每一行和每一列都按非降序排序。按排序顺序打印矩阵的所有元素。
null
例子：
Input: mat[][] = { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}, };Output:Elements of matrix in sorted order10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
我们可以使用 年轻的画面 解决上述问题。其思想是考虑给定的二维数组作为年轻表，并调用提取最小O（n）。
C++
// A C++ program to Print all elements in sorted order from row and // column wise sorted matrix #include<iostream> #include<climits> using namespace std; #define INF INT_MAX #define N 4 // A utility function to youngify a Young Tableau. This is different // from standard youngify. It assumes that the value at mat[0][0] is // infinite. void youngify( int mat[][N], int i, int j) { // Find the values at down and right sides of mat[i][j] int downVal = (i+1 < N)? mat[i+1][j]: INF; int rightVal = (j+1 < N)? mat[i][j+1]: INF; // If mat[i][j] is the down right corner element, return if (downVal==INF && rightVal==INF) return ; // Move the smaller of two values (downVal and rightVal) to // mat[i][j] and recur for smaller value if (downVal < rightVal) { mat[i][j] = downVal; mat[i+1][j] = INF; youngify(mat, i+1, j); } else { mat[i][j] = rightVal; mat[i][j+1] = INF; youngify(mat, i, j+1); } } // A utility function to extract minimum element from Young tableau int extractMin( int mat[][N]) { int ret = mat[0][0]; mat[0][0] = INF; youngify(mat, 0, 0); return ret; } // This function uses extractMin() to print elements in sorted order void printSorted( int mat[][N]) { cout << "Elements of matrix in sorted order n" ; for ( int i=0; i<N*N; i++) cout << extractMin(mat) << " " ; } // driver program to test above function int main() { int mat[N][N] = { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}, }; printSorted(mat); return 0; } |
JAVA
// A Java program to Print all elements // in sorted order from row and // column wise sorted matrix class GFG { static final int INF = Integer.MAX_VALUE; static final int N = 4 ; // A utility function to youngify a Young Tableau. // This is different from standard youngify. // It assumes that the value at mat[0][0] is infinite. static void youngify( int mat[][], int i, int j) { // Find the values at down and right sides of mat[i][j] int downVal = (i + 1 < N) ? mat[i + 1 ][j] : INF; int rightVal = (j + 1 < N) ? mat[i][j + 1 ] : INF; // If mat[i][j] is the down right corner element, // return if (downVal == INF && rightVal == INF) { return ; } // Move the smaller of two values // (downVal and rightVal) to mat[i][j] // and recur for smaller value if (downVal < rightVal) { mat[i][j] = downVal; mat[i + 1 ][j] = INF; youngify(mat, i + 1 , j); } else { mat[i][j] = rightVal; mat[i][j + 1 ] = INF; youngify(mat, i, j + 1 ); } } // A utility function to extract // minimum element from Young tableau static int extractMin( int mat[][]) { int ret = mat[ 0 ][ 0 ]; mat[ 0 ][ 0 ] = INF; youngify(mat, 0 , 0 ); return ret; } // This function uses extractMin() // to print elements in sorted order static void printSorted( int mat[][]) { System.out.println( "Elements of matrix in sorted order n" ); for ( int i = 0 ; i < N * N; i++) { System.out.print(extractMin(mat) + " " ); } } // Driver Code public static void main(String args[]) { int mat[][] = {{ 10 , 20 , 30 , 40 }, { 15 , 25 , 35 , 45 }, { 27 , 29 , 37 , 48 }, { 32 , 33 , 39 , 50 }}; printSorted(mat); } } // This code is contributed by Rajput-Ji |
Python3
# Python 3 program to Print all elements # in sorted order from row and column # wise sorted matrix import sys INF = sys.maxsize N = 4 # A utility function to youngify a Young # Tableau. This is different from standard # youngify. It assumes that the value at # mat[0][0] is infinite. def youngify(mat, i, j): # Find the values at down and # right sides of mat[i][j] downVal = mat[i + 1 ][j] if (i + 1 < N) else INF rightVal = mat[i][j + 1 ] if (j + 1 < N) else INF # If mat[i][j] is the down right # corner element, return if (downVal = = INF and rightVal = = INF): return # Move the smaller of two values # (downVal and rightVal) to mat[i][j] # and recur for smaller value if (downVal < rightVal): mat[i][j] = downVal mat[i + 1 ][j] = INF youngify(mat, i + 1 , j) else : mat[i][j] = rightVal mat[i][j + 1 ] = INF youngify(mat, i, j + 1 ) # A utility function to extract minimum # element from Young tableau def extractMin(mat): ret = mat[ 0 ][ 0 ] mat[ 0 ][ 0 ] = INF youngify(mat, 0 , 0 ) return ret # This function uses extractMin() to # print elements in sorted order def printSorted(mat): print ( "Elements of matrix in sorted order n" ) i = 0 while i < N * N: print (extractMin(mat), end = " " ) i + = 1 # Driver Code if __name__ = = "__main__" : mat = [[ 10 , 20 , 30 , 40 ], [ 15 , 25 , 35 , 45 ], [ 27 , 29 , 37 , 48 ], [ 32 , 33 , 39 , 50 ]] printSorted(mat) # This code is contributed by ita_c |
C#
// A C# program to Print all elements // in sorted order from row and // column wise sorted matrix using System; class GFG { static int INF = int .MaxValue; static int N = 4; // A utility function to youngify a Young Tableau. // This is different from standard youngify. // It assumes that the value at mat[0][0] is infinite. static void youngify( int [,]mat, int i, int j) { // Find the values at down and right sides of mat[i][j] int downVal = (i + 1 < N) ? mat[i + 1,j] : INF; int rightVal = (j + 1 < N) ? mat[i,j + 1] : INF; // If mat[i][j] is the down right corner element, // return if (downVal == INF && rightVal == INF) { return ; } // Move the smaller of two values // (downVal and rightVal) to mat[i][j] // and recur for smaller value if (downVal < rightVal) { mat[i,j] = downVal; mat[i + 1,j] = INF; youngify(mat, i + 1, j); } else { mat[i, j] = rightVal; mat[i, j + 1] = INF; youngify(mat, i, j + 1); } } // A utility function to extract // minimum element from Young tableau static int extractMin( int [,]mat) { int ret = mat[0,0]; mat[0, 0] = INF; youngify(mat, 0, 0); return ret; } // This function uses extractMin() // to print elements in sorted order static void printSorted( int [,]mat) { Console.WriteLine( "Elements of matrix in sorted order n" ); for ( int i = 0; i < N * N; i++) { Console.Write(extractMin(mat) + " " ); } } // Driver Code static public void Main () { int [,]mat = {{10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}}; printSorted(mat); } } // This code is contributed by ajit. |
Javascript
<script> // A Javascript program to Print all elements // in sorted order from row and // column wise sorted matrix let INF = Number.MAX_VALUE; let N = 4; // A utility function to youngify a Young Tableau. // This is different from standard youngify. // It assumes that the value at mat[0][0] is infinite. function youngify(mat,i,j) { // Find the values at down and right sides of mat[i][j] let downVal = (i + 1 < N) ? mat[i + 1][j] : INF; let rightVal = (j + 1 < N) ? mat[i][j + 1] : INF; // If mat[i][j] is the down right corner element, // return if (downVal == INF && rightVal == INF) { return ; } // Move the smaller of two values // (downVal and rightVal) to mat[i][j] // and recur for smaller value if (downVal < rightVal) { mat[i][j] = downVal; mat[i + 1][j] = INF; youngify(mat, i + 1, j); } else { mat[i][j] = rightVal; mat[i][j + 1] = INF; youngify(mat, i, j + 1); } } // A utility function to extract // minimum element from Young tableau function extractMin(mat) { let ret = mat[0][0]; mat[0][0] = INF; youngify(mat, 0, 0); return ret; } // This function uses extractMin() // to print elements in sorted order function printSorted(mat) { document.write( "Elements of matrix in sorted order n<br>" ); for (let i = 0; i < N * N; i++) { document.write(extractMin(mat) + " " ); } } let mat=[[10, 20, 30, 40],[15, 25, 35, 45], [27, 29, 37, 48],[32, 33, 39, 50]]; printSorted(mat); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
Elements of matrix in sorted order10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
提取最小值的时间复杂度为O（N），称为O（N） 2. )时报。因此，总体时间复杂度为O（N 3. ).
A. 更好的解决方案 就是使用 用于合并k个排序数组的方法 。其想法是使用大小为N的最小堆来存储第一列的元素。它们确实提取了最小值。在extract minimum中，将最小元素替换为从中提取元素的行的下一个元素。该解的时间复杂度为O（N） 2. LogN）。
C++
// C++ program to merge k sorted arrays of size n each. #include<iostream> #include<climits> using namespace std; #define N 4 // A min heap node struct MinHeapNode { int element; // The element to be stored int i; // index of the row from which the element is taken int j; // index of the next element to be picked from row }; // Prototype of a utility function to swap two min heap nodes void swap(MinHeapNode *x, MinHeapNode *y); // A class for Min Heap class MinHeap { MinHeapNode *harr; // pointer to array of elements in heap int heap_size; // size of min heap public : // Constructor: creates a min heap of given size MinHeap(MinHeapNode a[], int size); // to heapify a subtree with root at given index void MinHeapify( int ); // to get index of left child of node at index i int left( int i) { return (2*i + 1); } // to get index of right child of node at index i int right( int i) { return (2*i + 2); } // to get the root MinHeapNode getMin() { return harr[0]; } // to replace root with new node x and heapify() new root void replaceMin(MinHeapNode x) { harr[0] = x; MinHeapify(0); } }; // This function prints elements of a given matrix in non-decreasing // order. It assumes that ma[][] is sorted row wise sorted. void printSorted( int mat[][N]) { // Create a min heap with k heap nodes. Every heap node // has first element of an array MinHeapNode *harr = new MinHeapNode[N]; for ( int i = 0; i < N; i++) { harr[i].element = mat[i][0]; // Store the first element harr[i].i = i; // index of row harr[i].j = 1; // Index of next element to be stored from row } MinHeap hp(harr, N); // Create the min heap // Now one by one get the minimum element from min // heap and replace it with next element of its array for ( int count = 0; count < N*N; count++) { // Get the minimum element and store it in output MinHeapNode root = hp.getMin(); cout << root.element << " " ; // Find the next element that will replace current // root of heap. The next element belongs to same // array as the current root. if (root.j < N) { root.element = mat[root.i][root.j]; root.j += 1; } // If root was the last element of its array else root.element = INT_MAX; //INT_MAX is for infinite // Replace root with next element of array hp.replaceMin(root); } } // FOLLOWING ARE IMPLEMENTATIONS OF STANDARD MIN HEAP METHODS // FROM CORMEN BOOK // Constructor: Builds a heap from a given array a[] of given size MinHeap::MinHeap(MinHeapNode a[], int size) { heap_size = size; harr = a; // store address of array int i = (heap_size - 1)/2; while (i >= 0) { MinHeapify(i); i--; } } // A recursive method to heapify a subtree with root at given index // This method assumes that the subtrees are already heapified void MinHeap::MinHeapify( int i) { int l = left(i); int r = right(i); int smallest = i; if (l < heap_size && harr[l].element < harr[i].element) smallest = l; if (r < heap_size && harr[r].element < harr[smallest].element) smallest = r; if (smallest != i) { swap(&harr[i], &harr[smallest]); MinHeapify(smallest); } } // A utility function to swap two elements void swap(MinHeapNode *x, MinHeapNode *y) { MinHeapNode temp = *x; *x = *y; *y = temp; } // driver program to test above function int main() { int mat[N][N] = { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}, }; printSorted(mat); return 0; } |
输出：
10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50
练习： 上述解决方案适用于方形矩阵。将上述解推广到M*N矩形矩阵。 本文由 瓦伦 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
