2023 跟我一同学算法：数据结构和算法-数组(上)

什么是数组？

数组是存储在接连内存位置的相同变量类型的项目的调集。它是最流行和最简略的数据结构之一，一般用于完成其他数据结构。数组中的每个项目都从 0 开端索引。

每个程序员的愿望不仅是成为一名优异的程序员，并且成为一名巨大的程序员。咱们都想完成咱们的目标，为了完成咱们的目标，咱们必须有一个巨大的计划。

咱们能够经过索引值直接拜访数组元素。

数组的根本术语

• 数组索引： 在数组中，元素由其索引来标识。数组索引从0开端。
• 数组元素： 元素是存储在数组中的项目，能够经过其索引进行拜访。
• 数组长度： 数组的长度由它能够包括的元素数量决定。

数组的表明

数组的表明能够经过其声明来界说。声明意味着为给定巨细的数组分配内存。

数组能够用不同的语言以不同的方法声明。为了更好地说明，下面是一些特定于语言的数组声明。

然而，上面的声明是静态或编译时内存分配，这意味着数组元素的内存是在程序编译时分配的。这儿只会分配固定巨细（即方括号 [] 中说到的巨细）的内存用于存储，可是咱们不认为这不会与咱们知道数组的巨细相同的状况每次，可能会出现咱们不知道数组巨细的状况。假如咱们声明较大的巨细并存储较少数量的元素，将导致内存浪费，或许是咱们声明较小的巨细的状况，那么咱们将不会取得满足的内存来存储其余元素。在这种状况下，静态内存分配不是首选。

为什么需求数组数据结构？

假设有一个班有五名学生，假如咱们必须记载他们的考试成绩，咱们能够经过声明五个变量并跟踪记载来做到这一点，但假如学生人数变得十分多，那会怎样？操纵和保护数据具有挑战性。

这意味着，当咱们有少数对象时，咱们能够运用一般变量（v1，v2，v3，..）。但假如咱们想要存储很多实例，用一般变量来办理它们就变得很困难。数组的主意是在一个变量中表明许多实例..

数组类型：

数组主要有两种类型：

• 一维数组（1-D array） : 们能够将一维数组想象为一行，其间一个接一个地存储元素。

一维数组

• 二维数组： 2-D多维数组能够被视为数组的数组，也能够被视为由行和列组成的矩阵。

二维阵列

• 三维数组： 3-D多维数组包括三个维度，因而能够将其视为二维数组的数组。

数组运算的类型：

• 遍历：遍历数组的元素。
• 刺进：在数组中刺进一个新元素。
• 删去：从数组中删去元素。
• 搜索：在数组中搜索元素。
• 排序：坚持数组中元素的次序。

运用数组的长处:

• 数组允许随机拜访元素。这使得按位置拜访元素变得更快。
• 数组具有更好的缓存局部性，这在功能上有很大的差异。
• 数组运用单个称号表明相同类型的多个数据项。
• 数组存储多个具有相同称号的类似类型的数据。
• 数组数据结构用于完成其他数据结构，如链表、堆栈、队列、树、图等。

数组的缺陷:

• 由于数组的巨细是固定的，一旦分配了内存，就无法增加或减少，因而无法在需求时存储额定的数据。固定巨细的数组称为静态数组。
• 为数组分配少于所需的内存会导致数据丢失。数组本质上是同构的，因而单个数组不能存储不同数据类型的值。
• 数组将数据存储在接连的内存位置，这使得删去和刺进十分难以完成。经过完成链表能够战胜这个问题，链表允许次序拜访元素。

数组算法

查找给定三个数组中的重复元素

算法讲解：

1. 们需求清楚数组是现已排序好的还是没有排序好的，假如没有排序咱们需求将三个数组进行升序排。
2. 对排完序的数组咱们依次比较
3. 然后对最新元素的索引+1或许到下一个元素
4. 一向比较完

func getSameItemSlice(s1, s2, s3 []int) []int {
	var x, y, z int = 0, 0, 0
	var rest []int
	for {
		if x < len(s1) && y < len(s2) && z < len(s3) {
			if s1[x] == s2[y] && s2[y] == s3[z] {
				rest = append(rest, s1[x])
				x++
				y++
				z++
			} else if s1[x] < s2[y] {
				x++
			} else if s2[y] < s3[z] {
				y++
			} else {
				z++
			}
			continue
		}
		break
	}
	return rest
}
// 测验
func Test2(t *testing.T) {
	var ar1 = []int{1, 5, 10, 20, 40, 80}
	var ar2 = []int{6, 7, 20, 80, 100}
	var ar3 = []int{3, 4, 15, 20, 30, 70, 80, 120}
	rest := getSameItemSlice(ar1, ar2, ar3)
	fmt.Println(rest)
}

复杂度分析： 比较三个数组，咱们的循环次数依赖于最小长度的数组，咱们只需求循环一次即可，所以咱们的时刻复杂度为： O(N),N 的长度取决于最短的那个数组。

空间复杂度：咱们需求保存最后的相同的元素的结果，所以咱们需求 var rest []int 来保存。 所以空间复杂度为 O（1）