首页 > 编程语言 > 小白学算法-什么是矩阵数据结构以及有哪些应用?

小白学算法-什么是矩阵数据结构以及有哪些应用?

时间:2023-10-18 17:01:30浏览次数:38  
标签:arr mat ++ 元素 矩阵 let 小白学 数据结构

什么是矩阵数据结构以及有哪些应用

 小白学算法-什么是矩阵数据结构以及有哪些应用?_编程

矩阵表示按行和列的顺序排列的数字的集合。必须将矩阵的元素括在圆括号或方括号中。 例如:

具有 9 个元素的矩阵如下所示。

 小白学算法-什么是矩阵数据结构以及有哪些应用?_解决方案_02

该矩阵

M

有 3 行和 3 列。

矩阵M

的每个元素都可以通过其行号和列号来引用。例如,

M[2][3] = 6

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

矩阵或网格的声明

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

int arr[行数][列数];

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

 小白学算法-什么是矩阵数据结构以及有哪些应用?_方程组_03

矩阵的表示

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

初始化矩阵或网格

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

方法一

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

方法2

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 代码
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.在矩阵中搜索:

给定一个大小为 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(nxm)。

<script>
	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;
	}

// 驱动程序测试上述内容

	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))
		console.log("YES" + "<br>");
	else
		console.log("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。

//打印主对角线的函数
function printPrincipalDiagonal(mat, n)
{
	let s = "";
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {

			if (i == j)
			{
				s += mat[i][j];
				s += " ";
			}
		}
	}
	console.log("Principal Diagonal: "+s);
	
}

//打印次要对角线的函数
function printSecondaryDiagonal(mat,n)
{
	let s="";
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {

			if ((i + j) == (n - 1))
			{
				s += mat[i][j];
				s +=" ";
			}
		}
	}
	console.log("Secondary Diagonal: "+s);
}

let n = 4;
let a = [[ 1, 2, 3, 4 ],
    [ 5, 6, 7, 8 ],
    [ 1, 2, 3, 4 ],
    [ 5, 6, 7, 8 ] ];

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

时间复杂度:O(n2),由于涉及嵌套循环,所以时间复杂度是平方。 辅助空间: O(1)。

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\[] 的元素一一复制回给定的矩阵。

// JS 实现对给定的矩阵//函数进行排序,以对给定的矩阵进行排序
function sortMat(mat, n)
{

// 大小为 n ^ 2的//临时矩阵
	let temp = [];
	let k = 0;
	
// 逐个复制矩阵元素
	// leto temp[]
	for (let i = 0; i < n; i++)
		for (let j = 0; j < n; j++)
			temp[k++] = mat[i][j];
			
	// sort temp[]
	temp.sort(function (a, b) { return b - a });
	
	// 逐个复制 temp[] 中的元素
	// in mat[][]
	k = 0;
	for (let i = 0; i < n; i++)
		for (let j = 0; j < n; j++)
			mat[i][j] = temp[k++];
}

// 打印给定矩阵的函数
function printMat(mat, n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++)
			console.log(mat[i][j]);
	}
}

// 驱动程序测试上述内容
let mat = [[5, 4, 7], [1, 3, 8], [2, 9, 6]];
let n = 3;
printMat(mat, n);
sortMat(mat, n);
printMat(mat, n);

时间复杂度: 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

// 将矩阵向左旋转 180 的 Javascript 程序
let R= 4
let C= 4

// 将矩阵旋转 180 度的函数
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 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 printMatrix(arr)
{
	console.log(arr);
}

// 逆时针旋转矩阵的函数
// 旋转 180 度
function rotate180(arr)
{
	transpose(arr);
	reverseColumns(arr);
	transpose(arr);
	reverseColumns(arr);
}
let arr = [[1, 2, 3, 4 ],
        [ 5, 6, 7, 8 ],
        [ 9, 10, 11, 12 ],
        [ 13, 14, 15, 16 ]];
rotate180(arr);
printMatrix(arr);

时间复杂度: 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 的元素。

// 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");
}

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

矩阵和行列式的应用

矩阵和行列式的一种应用是它可以用来求解两个或三个变量的线性方程。矩阵和行列式还用于检查任何系统的一致性,无论它们是否一致。

使用矩阵的逆矩阵求解线性方程组

线性方程组的解可以通过矩阵的逆来求得。设方程为:

a 1 x + b 1 y + c 1 z = d 1

a 2 x + b 2 y + c 2 z = d 2

a 3 x + b 3 y + c 3 z = d 3

这些方程可以使用矩阵表示如下

 小白学算法-什么是矩阵数据结构以及有哪些应用?_解决方案_04

进一步这可以写成

 小白学算法-什么是矩阵数据结构以及有哪些应用?_方程组_05

进一步这个系统可以写成 AX=B

其中矩阵 A 包含未知变量的系数。

A=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_程序员_06

矩阵 X 是包含未知变量的列矩阵。

X =

 小白学算法-什么是矩阵数据结构以及有哪些应用?_叔叔结构算法_07

矩阵B也是一个列矩阵,它包含常数。

B=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_程序员_08

因此,如上所述,线性方程组可以转换为矩阵的形式,可以写为:

AX=B

如果 A 是非奇异矩阵,则 A -1存在。

两边都乘以 A -1

(A -1) \* AX = (A -1) \* B

IX = (A -1) \* B

X = (A -1) \* B

这为未知变量提供了唯一的解决方案。该解决方案将是唯一的,因为任何非奇异矩阵都有唯一的逆矩阵。

如果 A 是奇异矩阵,则 A -1不存在。在这种情况下|A| = 0,所以你必须计算 (adj A)B。

  1. 如果 (adj A)B ≠ O,则线性方程组不存在任何一个,并且该系统将不一致。
  2. 如果 (adj A)B = O,则线性方程组将具有零解或无穷多个解,这就是为什么如果系统没有任何解,则系统可能会不一致,如果有无穷多个解,则系统可能会一致解决方案。

系统的一致性

根据方程组拥有的解的数量,可以认为方程组是一致的或不一致的。

  • \*\一致系统:\\*如果方程组有解,则称该方程组是一致的。
  • \*\不一致系统:\\*如果一个方程组没有解,则称该方程组是不一致的。

示例问题

问题 1. 使用矩阵求解以下线性方程

2x + y = 3

2x + 3y = 6

解决方案:

上述线性方程组可以写成 AX = B 的形式,其中 A 是系数矩阵,X 是未知变量矩阵,B 是常数矩阵。

A=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_编程_09

X =

 小白学算法-什么是矩阵数据结构以及有哪些应用?_解决方案_10

B=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_叔叔结构算法_11

首先找出|A|

如你所见|A| = 4 ≠ 0。因此,方程组是一致的并且将具有唯一解,并且可以使用 X = A -1 B找到解

 小白学算法-什么是矩阵数据结构以及有哪些应用?_程序员_12

一个-1 =

 小白学算法-什么是矩阵数据结构以及有哪些应用?_程序员_13

X = A -1 B

 小白学算法-什么是矩阵数据结构以及有哪些应用?_解决方案_14

=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_方程组_15

 小白学算法-什么是矩阵数据结构以及有哪些应用?_编程_16

=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_编程_17

 小白学算法-什么是矩阵数据结构以及有哪些应用?_方程组_18

=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_程序员_19

从这里你可以得出结论

x = 3/4

y = 6/4

问题2. 说出给定系统是否一致

x + 3y = 5

2x + 6y = 8

解决方案:

上述方程组可以写成AX=B的形式,其中

A=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_编程_20

X =

 小白学算法-什么是矩阵数据结构以及有哪些应用?_编程_21

B=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_编程_22

现在检查 A 的行列式

|一个| = 6 – 6 = 0克

为了检查系统的一致性,你必须检查 (adj A)B

形容词 A =

 小白学算法-什么是矩阵数据结构以及有哪些应用?_解决方案_23

(形容词 A)B =

 小白学算法-什么是矩阵数据结构以及有哪些应用?_叔叔结构算法_24

(形容词 A)B =

 小白学算法-什么是矩阵数据结构以及有哪些应用?_程序员_25

(形容词 A)B =

 小白学算法-什么是矩阵数据结构以及有哪些应用?_程序员_26

由于 (adj A)B ≠ 0,因此给定线性方程组的解不存在。因此,方程组是不一致的。

问题 3. 使用矩阵法求解线性方程组

x – y + 2z = 7

3x + 4y – 5z = -5

2x – y + 3z = 12

解决方案:

上述方程组可以写成AX=B的形式,其中

A=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_程序员_27

X =

 小白学算法-什么是矩阵数据结构以及有哪些应用?_解决方案_28

B=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_解决方案_29

现在检查 A 的行列式

|一个| = 1 \* (12 – 5) + 1 \* (9 + 10) + 2 \* (-3 – 8)

|一个| = 7 + 19 – 22 = 4

|一个| ≠0

因此,它的逆存在,因此存在唯一解,可以通过 X = A -1 B找到

 小白学算法-什么是矩阵数据结构以及有哪些应用?_方程组_30

一个-1 =

 小白学算法-什么是矩阵数据结构以及有哪些应用?_编程_31

X = A -1 B

 小白学算法-什么是矩阵数据结构以及有哪些应用?_方程组_32

=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_编程_33

 小白学算法-什么是矩阵数据结构以及有哪些应用?_叔叔结构算法_34

=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_编程_35

 小白学算法-什么是矩阵数据结构以及有哪些应用?_叔叔结构算法_36

=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_方程组_37

 小白学算法-什么是矩阵数据结构以及有哪些应用?_方程组_38

=

 小白学算法-什么是矩阵数据结构以及有哪些应用?_解决方案_39

从这里,您可以看到 x = 2、y = 1 和 z = 3。

因此,x = 2、y = 1、z = 3。

标签:arr,mat,++,元素,矩阵,let,小白学,数据结构
From: https://blog.51cto.com/demo007x/7913258

相关文章

  • 邻接矩阵
    邻接矩阵(AdjacencyMatrix)是表示顶点之间相邻关系的矩阵。  设一个图G=(V,E)逻辑结构分为两部分:V和E集合,其中,V是顶点,E是边。用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间关系(边或弧)的数据,这个二维数组称为邻接矩阵。......
  • 3.1-Pandas数据结构
    3.1-Pandas数据结构  3.1.1认识Pandas库¶基于Numpy的一种工具,为解决数据分析任务而创建的,纳入了大量库和一些标准的数据模型,提供了高效地操作大型数据集所需的工具基本上你能用Excel或者Bi工具进行的数据处理,Pandas也都能实现,而且更快 In [ ]:......
  • 矩阵求导笔记
    1.标量对矩阵的求导考虑一个标量函数\(f(A)\),其输入是一个\(m\timesn\)矩阵。函数关于矩阵的导数定义为:\[\frac{\partialf}{\partialA}=\begin{bmatrix}\frac{\partialf}{\partialA_{11}}&\cdots&\frac{\partialf}{\partialA_{1n}}\\\vdots&\d......
  • 【数据结构】7.平衡搜索树(AVL树和红黑树)
    0.概述对于普通的搜索树,如果一直插入比第一个元素小的元素,它会退化成一个无限向左下角眼神的单链表,使得时间复杂度退化为O(n)。如果我们在插入时保持树的结构是平衡的,则可以保证查找、插入和删除的时间复杂度有对数级的时间性能,下面讲到的AVL树和红黑树都是平衡搜索树,通过旋......
  • 1数据结构
    数据结构数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。基本概念数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。数据元素:是组成数据的、有一定意义的基本单位,在计算......
  • C#学习笔记--数据结构、泛型、委托事件等进阶知识点
    C#进阶简单数据结构类ArrayList元素类型以Object类型存储,支持增删查改的数组容器。因而存在装箱拆箱操作,谨慎使用。//ArrayListArrayListarray=newArrayList();//增=================array.Add("Hello");array.Add(true);array.Add("Tony");//添加单个元素array.Add(......
  • 十天学完基础数据结构-第四天(链表(Linked List))
    链表的基本概念链表是一种线性数据结构,与数组不同,链表的元素(节点)之间通过指针相互连接。链表有以下基本概念:节点:链表中的每个数据项称为节点,每个节点包含数据和一个指向下一个节点的指针。头节点:链表的第一个节点称为头节点,它通常用来表示整个链表的起始位置。尾节点:链表的最后一个......
  • 数据结构
    数据结构数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。基本概念数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。数据元素:是组成数据的、有一定意义的基本单位,在计算......
  • Julia notebook:矩阵乘法
    在本次notebook中,我们将:并行化一个简单的算法学习不同并行策略的performance使用Julia进行实现 问题描述假设所有矩阵,包括A,B和C都初始存储在masterprocess最终的结果会将在C中被覆盖步骤为了实现并行化,我们将遵循以下步骤:确定顺序算法中可以并行化的部分考虑......
  • 稀疏矩阵快速转置
    如果需要将一个使用三元组形式存储的稀疏矩阵进行转置,当然可以直接交换每一个结点的行和列。但这样做的问题在于,原矩阵是按行数升序排列的,转置之后的矩阵就会变为无序的。快速转置算法的目的就在于得到一个同样有序排列的转置后矩阵。三元组和稀疏数组定义#defineMAXSIZE1250......