原文:
给定一个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
我们可以使用 解决上述问题。 想法是将给定的 2d 数组视为 young tableau,并调用提取最小值o(n)
。
c
// a c program to print all elements in sorted order from row and
// column wise sorted matrix
#include
#include
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
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#
// 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 ^ 3)
。
更好的pg电子试玩链接的解决方案是使用方法来。 想法是使用大小为n
的最小堆来存储第一列的元素。 做最小提取。 在最小提取中,将最小元素替换为要从中提取元素的行的下一个元素。 该pg电子试玩链接的解决方案的时间复杂度为o(n ^ 2 logn)
。
// c program to merge k sorted arrays of size n each.
#include
#include
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
练习:
上述pg电子试玩链接的解决方案适用于方阵。 扩展上述pg电子试玩链接的解决方案以用于m * n
矩形矩阵。
麻将胡了pg电子网站的版权属于:月萌api www.moonapi.com,转载请注明出处