1. 数据结构与算法/

矩阵或网格数据结构

·1577 字·8 分钟· loading
数据结构与算法 数据结构与算法 矩阵或网格数据结构
demo007x
作者
demo007x

矩阵或网格数据结构
#

什么是矩阵?
#

矩阵是由行和列组成的二维数组。它是条目水平或垂直行中元素的排列。

矩阵或网格简介 - 数据结构和算法教程

矩阵或网格的声明
#

声明矩阵或二维数组的语法与一维数组的语法非常相似,如下所示。

int arr[行数][列数];   

但是,它会生成如下所示的数据结构:

矩阵的表示

从上图中可以看出,元素按行和列进行组织。如上图所示,单元格 x[0][0] 是第一行第一列的第一个元素。第一个方括号内的值表示行号,第二个方括号内的值表示列号。(即 x[行][列])。

初始化矩阵或网格
#

初始化二维数组有两种方法。

方法一

int arr[4][3]={1, 2, 3, 4, 5, 6, 20, 80, 90, 100, 110, 120};

方法二

int arr[4][3]={{1, 2, 3}, {4, 5, 6}, {20, 80, 90}, {100, 110, 120}};

以下是在声明期间初始化元素的两种方法。这里,首选第二种方法,因为第二种方法更具可读性和理解性,以便您可以直观地看到arr[][] 由四行三列组成。

如何访问矩阵或网格中的数据
#

与一维数组一样,可以通过使用矩阵的索引来访问各个元素来随机访问矩阵。单元格有两个索引,一个为其行号,另一个为其列号。我们可以使用X[i][j]来访问矩阵第 i行****第 j列的元素。

矩阵

矩阵

从矩阵中访问第 i第 j列元素的语法:

int  = X[i][j];

如何打印矩阵或网格的元素:
#

可以使用两个“for”循环来打印矩阵或二维数组的元素。

// JS code for above approach
let arr = [[1, 2, 3, 4],
		[5, 6, 7, 8],
		[9, 10, 11, 12]];
for (let i = 0; i < 3; i++) {
let s="";
	for (let j = 0; j < 4; j++) {
		s+=(arr[i][j]+" ");
	}
	console.log(s);
}

输出

1 2 3 4 
5 6 7 8 
9 10 11 12 

您必须了解的 Matrix/Grid 的一些基本问题:
#

1、在矩阵中搜索:
#

给定一个大小为 N x M 的矩阵 mat[][],其中每行和每列都按升序排序,并给出数字 X。任务是确定元素 X 是否存在于矩阵中。

例子:

输入: mat[][] = { {1, 5, 9}, {14, 20, 21}, {30, 34, 43} } x = 14 输出: YES

输入: mat[][] = { {1, 5, 9, 11}, {14, 20, 21, 26}, {30, 34, 43, 50} } x = 42 输出: NO

解决方案:

有很多方法可以解决这个问题,但我们在这里讨论一种非常幼稚或暴力的方法。

一个简单的解决方案是将x与矩阵的每个元素进行一一比较。如果匹配,则返回 true。如果我们到达末尾则返回 false。该解法的时间复杂度为O(n*m)。

下面代码是以上的实现:

<script>
	// JavaScript code for the above approach
	function searchInMatrix(arr, x) {
		let m = arr.length, n = arr[0].length;
		for (let i = 0; i < m; i++) {
			for (let j = 0; j < n; j++) {
				if (arr[i][j] == x)
					return true;
			}
		}
		return false;
	}

	// Driver program to test above

	let x = 8;
	let arr = [
    [0, 6, 8, 9, 11],
		[20, 22, 28, 29, 31],
		[36, 38, 50, 61, 63],
		[64, 66, 100, 122, 128]
  ];

	if (searchInMatrix(arr, x))
		document.write("YES" + "<br>");
	else
		document.write("NO" + "<br>");

</script>

时间复杂度: O(M*N),其中M和N分别是行数和列数。 辅助空间: O(1)

2、打印矩阵对角线的程序
#

给定一个二维方阵,打印主对角线和次对角线。

例子 :

输入: 1 2 3 4 4 3 2 1 7 8 9 6 6 5 4 3 输出: 主对角线:1, 3, 9, 3 次对角线:4, 2, 8, 6

输入: 1 1 1 1 1 1 1 1 1 输出: 主对角线:1, 1, 1 次对角线:1, 1, 1

解决方案:

主对角线由元素 A00、A11、A22、A33 形成。 主对角线的条件:行列条件是行=列。

次对角线由元素 A03、A12、A21、A30 形成。 次对角线的条件:行列条件为行 = numberOfRows – 列 -1。

# Python3 Program to print the Diagonals of a Matrix
MAX = 100

# Function to print the Principal Diagonal
def printPrincipalDiagonal(mat, n):
	print("Principal Diagonal: ",end="")

	for i in range(0,n):
		for j in range(0,n):

			# Condition for principal diagonal
			if (i == j):
				print(mat[i][j] , ", ", end="")
	print("")

# Function to print the Secondary Diagonal
def printSecondaryDiagonal(mat, n):
	print("Secondary Diagonal: ",end = "")

	for i in range(0,n):
		for j in range(0,n):

			# Condition for secondary diagonal
			if ((i + j) == (n - 1)):
				print(mat[i][j] , ", ", end = "")
	print("")

# Driver code
n = 4
a = [ [ 1, 2, 3, 4 ],
					[ 5, 6, 7, 8 ],
					[ 1, 2, 3, 4 ],
					[ 5, 6, 7, 8 ] ]

printPrincipalDiagonal(a, n)
printSecondaryDiagonal(a, n)

# This code is contributed by akashish__

输出

主对角线:1, 6, 3, 8,
次对角线:4、7、2、5、

3、对给定矩阵进行排序
#

给定 anxn 矩阵。问题是按照严格的顺序对给定的矩阵进行排序。这里严格顺序意味着矩阵的排序方式使得一行中的所有元素都按升序排序,对于行“i”,其中 1 <= i <= n-1,行“i”的第一个元素大于或等于行“i-1”的最后一个元素。

例子:

输入: mat[][] = { {5, 4, 7}, {1, 3, 8}, {2, 9, 6} } 输出:

​ 1 2 3 ​ 4 5 6 ​ 7 8 9

解决方案:

解决这个问题的想法是创建一个大小为 n^2 的 temp[] 数组。从第一行开始,将给定矩阵的元素逐一复制到 temp[] 中。对[]进行排序。现在将 temp[] 的元素一一复制回给定的矩阵。

下面是实现:

# Python Implementation to sort the given matrix
def sortMat(mat, n):
	
	# temporary matrix of size n^2
	temp = [0]*n*n
	k = 0
	
	# copy the elements of matrix one by one
	# leto temp[]
	for i in range(0, n):
		for j in range(0, n):
			temp[k] = mat[i][j]
			k += 1
	
	# sort temp[]
	temp.sort(reverse = True)
	
	# copy the elements of temp[] one by one
	# in mat[][]
	k = 0
	for i in range(0, n):
		for j in range(0, n):
			mat[i][j] = temp[k]
			k += 1
	
# function to print the given matrix
def printMat(mat, n):
	for i in range(0, n):
		for j in range(0, n):
			print(mat[i][j], end = ' ')
		print("")
	
# Driver program to test above
mat = [[5, 4, 7],
	[1, 3, 8],
	[2, 9, 6]]
n = 3
	
print("Original Matrix:")
printMat(mat, n)
sortMat(mat, n)
print("\nMatrix After Sorting:")
printMat(mat, n)

# This code is contributed by ishankhandelwals.

输出

原始矩阵:
5 4 7 
1 3 8 
2 9 6 

排序后的矩阵:
1 2 3 
4 5 6 
7 8 9 

时间复杂度: O(n2log2n)。 辅助空间: O(n2),因为已占用 n * n 额外空间。

4、将矩阵旋转 180 度
#

给定一个方阵,任务是在不使用任何额外空间的情况下将其逆时针方向旋转 180 度。

例子 :

输入:

​ 1 2 3 ​ 4 5 6 ​ 7 8 9 输出:

​ 9 8 7 ​ 6 5 4 ​ 3 2 1

输入:

​ 1 2 3 4 ​ 5 6 7 ​ 8 9 0 1 2 ​ 3 4 5 6 输出:

​ 6 5 4 3 ​ 2 1 0 9 ​ 8 7 6 5 ​ 4 3 2 1

解决方案:

解决此问题需要四个步骤: 1- 求矩阵的转置。 2- 反转转置的列。 3-求矩阵的转置。 4- 转置的反转列

插图:

设给定矩阵为 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

首先我们找到转置。 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16

然后我们反转每列的元素。 4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13

然后再次转置 4 3 2 1 8 7 6 5 12 11 10 9 16 15 14 13

然后我们再次反转每列的元素 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

# Python program for left rotation of matrix by 180
R = 4
C = 4

# Function to rotate the matrix by 180 degree
def reverseColumns(arr):
for i in range(C):
	for j in range(0, int(C / 2)):
	x = arr[j][i]
	arr[j][i] = arr[C - 1 - j][i]
	arr[C - 1 - j][i] = x

# Function for transpose of matrix
def transpose(arr):
for i in range(R):
	for j in range(i, C):
	x = arr[j][i]
	arr[j][i] = arr[i][j]
	arr[i][j] = x

# Function for display the matrix
def printMatrix(arr):
for i in range(R):
	for j in range(C):
	print(arr[i][j], end = ' ')
	print()

# Function to anticlockwise rotate matrix
# by 180 degree
def rotate180(arr):
transpose(arr)
reverseColumns(arr)
transpose(arr)
reverseColumns(arr)

# Driven code
arr = [[1, 2, 3, 4 ],
			[ 5, 6, 7, 8 ],
			[ 9, 10, 11, 12 ],
			[ 13, 14, 15, 16 ]]
rotate180(arr)
printMatrix(arr)

# This code is contributed by akashish__
// Javascript program for left rotation of matrix by 180


let R= 4
let C= 4

// Function to rotate the matrix by 180 degree
function reverseColumns(arr)
{
	for (let i = 0; i < C; i++)
		for (let j = 0, k = C - 1; j < k; j++, k--)
			{
			let x= arr[j][i];
			arr[j][i] = arr[k][i];
			arr[k][i]=x;
			}
			
}

// Function for transpose of matrix
function transpose(arr)
{
	for (let i = 0; i < R; i++)
		for (let j = i; j < C; j++)
			{
			let x= arr[j][i];
			arr[j][i] = arr[i][j];
			arr[i][j]=x;
		}
}

// Function for display the matrix
function printMatrix(arr)
{
	document.write(arr);
}

// Function to anticlockwise rotate matrix
// by 180 degree
function rotate180(arr)
{
	transpose(arr);
	reverseColumns(arr);
	transpose(arr);
	reverseColumns(arr);
}

// Driven code

	let arr = [[1, 2, 3, 4 ],
					[ 5, 6, 7, 8 ],
					[ 9, 10, 11, 12 ],
					[ 13, 14, 15, 16 ]];
	rotate180(arr);
	printMatrix(arr);

输出

16 15 14 13 
12 11 10 9 
8 7 6 5 
4 3 2 1 

时间复杂度: O(R*C) 辅助空间: O(1)

5、查找矩阵中的唯一元素
#

给定一个具有 n 行和 m 列的矩阵 mat[][]。我们需要找到矩阵中唯一的元素,即矩阵中不重复的元素或频率为1的元素。

例子:

输入:

​ 20 15 30 2 ​ 2 3 5 30 ​ 6 7 6 8 输出: 3 20 5 7 8 15

输入:

​ 1 2 3
​ 5 6 2 ​ 1 3 5 ​ 6 2 2 **输出:**矩阵中没有唯一元素

解决方案:

这个想法是使用散列并遍历矩阵的所有元素,如果字典中存在某个元素,则增加其计数。否则插入一个值为 1 的元素。

# Python program to find unique
# element in matrix

# Function that calculate unique element
def unique(mat, n, m):
	maximum = 0
	flag = 0
	for i in range(n):
		for j in range(m):
			# Find maximum element in
			# a matrix
			if maximum < mat[i][j]:
				maximum = mat[i][j]

	# Take 1-D array of (maximum + 1)
	# size
	b = [0] * (maximum + 1)
	for i in range(n):
		for j in range(m):
			y = mat[i][j]
			b[y] += 1

	# print unique element
	for i in range(1, maximum+1):
		if b[i] == 1:
			print(i, end=' ')
	flag = 1

	if flag == 0:
		print("No unique element in the matrix")

R = 4
C = 4
mat = [[1, 2, 3, 20],
	[5, 6, 20, 25],
	[1, 3, 5, 6],
	[6, 7, 8, 15]]

# function that calculate unique element
unique(mat, R, C)

# This code is contributed by lokesh.
// JS code

let mat = [[1, 2, 3, 20], [5, 6, 20, 25], [1, 3, 5, 6], [6, 7, 8, 15]];

let max = 0;
let flag = 0;
for (let i = 0; i < mat.length; i++) {
for (let j = 0; j < mat.length; j++) {
	if (max < mat[i][j]) {
	max = mat[i][j];
	}
}
}

let b = new Array(max + 1).fill(0);
for (let i = 0; i < mat.length; i++) {
for (let j = 0; j < mat.length; j++) {
	let y = mat[i][j];
	b[y]++;
}
}

for (let i = 1; i <= max; i++) {
if (b[i] == 1) {
	console.log(i + " ");
	flag = 1;
}
}

if (!flag) {
console.log("No unique element in the matrix");
}

输出

2 7 8 15 25 

时间复杂度: O(m*n),其中 m 是行数,n 是列数。 辅助空间: O(max(矩阵))。

Related

链表数据结构
数据结构与算法 数据结构与算法 链表 golang
什么是链表?> 链表是一种线性数据结构,看起来像节点链,其中每个节点都是不同的元素。与数组不同,链表元
堆数据结构
数据结构与算法 数据结构 数据结构与算法
什么是堆数据结构?> 堆是一种特殊的基于树的数据结构,其中树是[完全二叉树](https://w
Hash 数据结构
数据结构与算法 数据结构与算法 Hash
什么是哈希?Hash 是一种使用Hash函数将键和值映射到散列表中的技术或过程。这样做是为了更快