什么是数组

一种线性的数据结构,用于将相同类型的元素,存储在连续的内存空间中。元素在数组中的位置,被称为索引。
数组的初始化通常有两种方式:无初始值、有初始值。在 Go 中的数组初始化:

// 无初始值
var arr []int
// 有初始值
nums := []int{1, 3, 2, 5, 4}

在 Go 中,指定长度时([5]int)为数组,不指定长度时([]int)为切片,由于 Go 的数组被设计为在编译期确定长度,因此只能使用常量来指定长度,为了方便实现下面博客中提到的扩容 extend() 方法,以下将切片(Slice)看作数组(Array)。

数组优点

  • 高效的查询
    数组中的元素类型相同,因此元素字长(长度)相同,并且数组中的元素被存储在连续的内存地址,所以我们可以在 O(1) 时间获取数组中任意一个元素,通过一个公式即可:元素内存地址 = 数组内存地址 + 元素字长 * 元素索引。

数组缺点

  • 初始化后长度不可变
    数组的内存空间是连续的,操作系统无法保证数组之后的内存空间是可用的。
  • 插入和删除操作效率低下
    数组的内存空间是连续的,假如我要在数组的第一个索引添加元素,不得不将第一个索引之后的所有元素都向后移动一位后,再把该元素赋值给该索引。
    删除与插入类似,不过是把元素都向前移动一位。
  • 浪费内存
    初始化一个比较长的数组,避免添加新元素后,末尾的元素丢失后出现意外。

数组的遍历

func traverse(nums []int) {
    count := 0
    // 通过索引遍历数组
    for i := 0; i < len(nums); i++ {
        count++
    }
   
    count = 0
    // 直接遍历数组
    for range nums {
        count++
    }
}

数组的查找

/* 在数组中查找指定元素 */
func find(nums []uint, target uint) (index int) {
    index = -1
    for i := 0; i < len(nums); i++ {
        if nums[i] == target {
            index = i
            break
        }
    }
    return
}

数组部分应用场景

  • 随机访问
  • 排序和搜索
  • 实现其他的数据结构

数组题目

数组的改变、移动

453.最小操作次数使数组元素相等

微软 Microsoft

“相对论”思路解决这个问题,你们都变丑了,我没变,那么我变帅了。根据题意可知,这个数组只有一种操作:每次操作将会使 n - 1 个元素增加 1。这个操作等价于让 1 个元素减少 1。
只要保证数组中,最小的元素不要再减少,其他元素减小,最终该元素都等于最小值,把所有元素的减少操作次数求和,即可得到最小操作次数。
首先对数组进行排序,获取最小值 min。然后遍历排序后的数组,当前元素 num 与最小值 min相减,获取变为最小值的操作次数,累加操作次数到 ans 中。

func minMoves(nums []int) (ans int) {
    sort.Ints(nums)
    min := nums[0]

    for _, num := range nums {
        ans += num-min
    }
    return
}

655.非递减数列

字节跳动、亚马逊

根据非递减数列的定义,可以得到 nums[i] < nums[i-1] 时,不满足非递减数列的定义。题意说可以修改一个 nums[i],修改后所有索引都满足 nums[i] >= nums[i-1] 即返回 true,否则返回 false。通过举例分析所有情况,如下。

  • 例子 1,nums := []int{4,2,5}
    可以调小 nums[0] ,将 nums[0] 修改为小于等于 nums[1] 的数,即得到非递减数列,修改后为 2,2,4。
    还可以调大 nums[1],将 nums[1] 修改为大于等于 nums[0] 的数,修改后可以为 4,4,5 或 4,5,5。
  • 例子 2,nums := []int{1,4,2,5}
    调小 nums[1],可以得到 1,2,2,5 或 1,1,2,5。
    调大 nums[2],可以得到 1,4,4,5 或 1,4,5,5。
  • 例子 3,nums := []int{3,4,2,5}
    调大 nums[2],可以得到 3,4,4,5 或 3,4,5,5。
    通过这三个例子可以看出,修改数组中的值,在例子 1 和 例子 2 中都有两种选择,分别是调大或者调小,但是例子 3 只能调大。
    当有元素破坏了数组的单调递增时,总是倾向将该元素调小。因为该元素后面位置的元素是未知的,少动它为妙,我们是倾向将该元素调小,当出现例子 3 的情况时,只能调大。
    下面用索引 i 来归纳出调整元素的判断条件。
  • 例子 1
    i = 1时,修改 nums[i-1]
  • 例子 2
    i > 1 时,修改 nums[i-1]
  • 例子 3
    i > 1 且 nums[i] < nums[i-2],修改 nums[i]
func checkPossibility(nums []int) bool {
    if len(nums) == 1 {
        return true
    }
    cnt := 0
    for i := 1; i < len(nums); i++ {
        if nums[i] >= nums[i-1] {
            continue
        }

        if nums[i] < nums[i-1] {
            if (i == 1) || (nums[i] >= nums[i-2]) {
                nums[i - 1] = nums[i]
            } else {
                nums[i] = nums[i - 1]
            }
            cnt++
        }
    }

    return cnt <= 1
}

283.移动零

亚马逊、Facebook、谷歌 Google

通过快、慢指针的思路来解决该问题。

我们创建两个指针 i 和 j,第一次遍历的时候指针 j 用来记录当前有多少 非 0 元素。即遍历的时候每遇到一个 非 0 元素就将其往数组左边挪,第一次遍历完后,j 指针的下标就指向了最后一个 非 0 元素下标。

第二次遍历的时候,起始位置就从 j 开始到结束,将剩下的这段区域内的元素全部置为 0。

  • 例子 1
    nums := []int{1,3,12}
    快、慢指针始终是相等的。
  • 例子 2
    nums := []int{0,1,0,3,12}
    快指针等于 4,即 len(nums)-1,慢指针等于 2, 即 len(nums)-1-零出现的次数,此时比较快、慢指针的大小,二次遍历,补全 0 即可。
func moveZeroes(nums []int)  {
    var slowIndex int

    for fastIndex := 0; fastIndex < len(nums); fastIndex++ {
        if nums[fastIndex] != 0 {
            nums[slowIndex] = nums[fastIndex]
            slowIndex++
        }
    }

    for i := slowIndex; i < len(nums); i++ {
        nums[i] = 0
    }
}

数组的旋转

统计数组中的元素

数组的遍历

二位数组及滚动数组

特定顺序遍历二维数组

二维数组变换

前缀和数组

最后修改:2023 年 10 月 27 日
如果觉得我的文章对你有用,请随意赞赏