從行和列的排序矩陣中按排序順序打印所有元素 · GeeksForGeeks 中文系列教程

# 從行和列的排序矩陣中按排序順序打印所有元素 > 原文： [https://www.geeksforgeeks.org/print-elements-sorted-order-row-column-wise-sorted-matrix/](https://www.geeksforgeeks.org/print-elements-sorted-order-row-column-wise-sorted-matrix/) 給定一個 n x n 矩陣，其中每一行和每一列均以非降序排列。按排序順序打印矩陣的所有元素。 **示例**： ``` Input: mat[][] = { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}, }; Output: Elements of matrix in sorted order 10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50 ``` 我們可以使用 [**Young Tableau**](http://en.wikipedia.org/wiki/Young_tableau) 解決上述問題。想法是將給定的 2D 數組視為 Young Tableau，并調用提取最小值`O(n)` ## C++ ```cpp // 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 ```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 ``` ## Python 3 ``` # 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# ```cs // 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. ``` **輸出**： ``` Elements of matrix in sorted order 10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50 ``` 提取最小值的時間復雜度為`O(n)`，稱為 `O(n^2)`倍。因此，總時間復雜度為 O（N <sup>3</sup> ）。 **更好的解決方案**是使用[方法來合并 k 個排序的數組](https://www.geeksforgeeks.org/merge-k-sorted-arrays/)。想法是使用大小為 N 的最小堆來存儲第一列的元素。做最小提取。在最小提取中，將最小元素替換為要從中提取元素的行的下一個元素。該解決方案的時間復雜度為 O（N <sup>2</sup> LogN）。 ``` // 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 elelement 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 矩形矩陣。