2023 跟我一同学算法：数据结构和算法-数组(上)
什么是数组？
数组是存储在接连内存位置的相同变量类型的项目的调集。它是最流行和最简略的数据结构之一，一般用于完成其他数据结构。数组中的每个项目都从 0 开端索引。
每个程序员的愿望不仅是成为一名优异的程序员，并且成为一名巨大的程序员。咱们都想完成咱们的目标，为了完成咱们的目标，咱们必须有一个巨大的计划。
咱们能够经过索引值直接拜访数组元素。
数组的根本术语
- 数组索引： 在数组中，元素由其索引来标识。数组索引从0开端。
- 数组元素： 元素是存储在数组中的项目，能够经过其索引进行拜访。
- 数组长度： 数组的长度由它能够包括的元素数量决定。
数组的表明
数组的表明能够经过其声明来界说。声明意味着为给定巨细的数组分配内存。
数组能够用不同的语言以不同的方法声明。为了更好地说明，下面是一些特定于语言的数组声明。
然而，上面的声明是静态或编译时内存分配，这意味着数组元素的内存是在程序编译时分配的。这儿只会分配固定巨细（即方括号 [] 中说到的巨细）的内存用于存储，可是咱们不认为这不会与咱们知道数组的巨细相同的状况每次，可能会出现咱们不知道数组巨细的状况。假如咱们声明较大的巨细并存储较少数量的元素，将导致内存浪费，或许是咱们声明较小的巨细的状况，那么咱们将不会取得满足的内存来存储其余元素。在这种状况下，静态内存分配不是首选。
为什么需求数组数据结构？
假设有一个班有五名学生，假如咱们必须记载他们的考试成绩，咱们能够经过声明五个变量并跟踪记载来做到这一点，但假如学生人数变得十分多，那会怎样？操纵和保护数据具有挑战性。
这意味着，当咱们有少数对象时，咱们能够运用一般变量（v1，v2，v3，..）。但假如咱们想要存储很多实例，用一般变量来办理它们就变得很困难。数组的主意是在一个变量中表明许多实例..
数组类型：
数组主要有两种类型：
- 一维数组（1-D array） : 们能够将一维数组想象为一行，其间一个接一个地存储元素。
一维数组
- 二维数组： 2-D多维数组能够被视为数组的数组，也能够被视为由行和列组成的矩阵。
二维阵列
- 三维数组： 3-D多维数组包括三个维度，因而能够将其视为二维数组的数组。
数组运算的类型：
- 遍历：遍历数组的元素。
- 刺进：在数组中刺进一个新元素。
- 删去：从数组中删去元素。
- 搜索：在数组中搜索元素。
- 排序：坚持数组中元素的次序。
运用数组的长处:
- 数组允许随机拜访元素。这使得按位置拜访元素变得更快。
- 数组具有更好的缓存局部性，这在功能上有很大的差异。
- 数组运用单个称号表明相同类型的多个数据项。
- 数组存储多个具有相同称号的类似类型的数据。
- 数组数据结构用于完成其他数据结构，如链表、堆栈、队列、树、图等。
数组的缺陷:
- 由于数组的巨细是固定的，一旦分配了内存，就无法增加或减少，因而无法在需求时存储额定的数据。固定巨细的数组称为静态数组。
- 为数组分配少于所需的内存会导致数据丢失。数组本质上是同构的，因而单个数组不能存储不同数据类型的值。
- 数组将数据存储在接连的内存位置，这使得删去和刺进十分难以完成。经过完成链表能够战胜这个问题，链表允许次序拜访元素。
数组算法
查找给定三个数组中的重复元素
算法讲解：
- 们需求清楚数组是现已排序好的还是没有排序好的，假如没有排序咱们需求将三个数组进行升序排。
- 对排完序的数组咱们依次比较
- 然后对最新元素的索引+1或许到下一个元素
- 一向比较完
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）
