Skip to content

用于编码面试的数组备忘单

原文:https://www.techinterviewhandbook.org/algorithms/array/

简介

数组在连续的内存位置保存相同类型的值。在数组中,我们通常关心两件事——元素的位置/索引和元素本身。不同的编程语言以不同的方式实现数组,并且会影响对数组进行操作的时间复杂度。在 Python、JavaScript、Ruby、PHP 等语言中,数组(或 Python 中的 list)的大小是动态的,创建数组时不需要预先定义大小。因此,人们通常更容易在面试中使用这些语言。

数组是面试中最常见的数据结构。询问其他主题的问题也可能涉及数组/序列。掌握阵法对于面试来说至关重要!

优势

  • 用一个变量名存储多个相同类型的元素
  • 只要有索引,访问元素就很快,而不是像链表那样从头开始遍历。

缺点

  • 向数组中间添加元素或从数组中间移除元素很慢,因为需要移动剩余的元素来容纳新的/缺失的元素。一个例外是,如果要插入/移除的位置在数组的末尾。
  • 对于某些固定数组大小的语言,它在初始化后不能改变其大小。如果插入操作导致元素总数超过大小,则必须分配一个新的数组,并复制现有的元素。创建一个新数组并传递元素的行为需要 O(n)时间。

学习资源

常用术语

在处理涉及数组的问题时,您会看到一些常见术语:

  • 子数组-数组中连续值的范围。
    • 例如:给定一个数组[2, 3, 6, 1, 5, 4][3, 6, 1]是一个子数组,而[3, 1, 5]不是子数组。
  • 子序列——通过删除一些元素或不删除任何元素,而不改变剩余元素的顺序,可以从给定序列中导出的序列。
    • 例如:给定一个数组[2, 3, 6, 1, 5, 4][3, 1, 5]是一个子序列,但是[3, 5, 1]不是一个子序列。

时间复杂度

操作 大 O 注意
接近 O(1)
搜索 O(n)
搜索(排序数组) O(log(n))
插入 O(n) 插入需要将所有后续元素向右移动一位,这需要 O(n)
插入(在末尾) O(1) 不需要移动其他元素的特殊插入情况
去除 O(n) 移除需要将所有后续元素左移一位,这需要 O(n)
移除(在最后) O(1) 不需要移动其他元素的特殊移除情况

面试时要注意的事情

  • 澄清数组中是否有重复值。重复值的存在会影响答案吗?它使问题更简单还是更难?
  • 当使用索引迭代数组元素时,注意不要越界。
  • 请注意在代码中分割或连接数组。通常,分割和连接数组需要 O(n)时间。在可能的情况下,使用开始和结束索引来划分子数组/范围。

拐角情况

  • 空序列
  • 具有 1 或 2 个元素的序列
  • 具有重复元素的序列
  • 序列中的重复值

技巧

注意,因为数组和字符串都是序列(字符串是字符数组),所以这里的大多数技术都适用于字符串问题。

滑动窗口

掌握适用于许多子数组/子串问题的滑动窗口技术。在滑动窗口中,通常向同一方向移动的两个指针永远不会互相超越。这保证了每个值最多只被访问两次,时间复杂度仍然是 O(n)。例子:无重复字符的最长子串最小尺寸子阵列总和最小窗口子串

两个指针

两个指针是滑动窗口的一个更一般的版本,指针可以互相交叉,可以在不同的数组上。例子:排序颜色回文子串

当您有两个数组要处理时,通常每个数组有一个索引(指针)来遍历/比较这两个数组,相关时递增其中一个指针。例如,我们使用这种方法来合并两个排序后的数组。例子:合并排序后的数组

从右侧穿越

有时你可以从右边开始遍历数组,而不是传统的从左边开始。例子:每日气温可见排队人数

排序数组

数组是排序的还是部分排序的?如果是的话,某种形式的二分搜索法应该是可能的。这通常也意味着面试官在寻找比 O(n)更快的解决方案。

你能给数组排序吗?有时,首先对数组进行排序可能会大大简化问题。显然,如果需要保持数组元素的顺序,这是行不通的。例子:合并间隔非重叠间隔

预计算

对于涉及子阵列的求和或乘法的问题,使用散列或前缀/后缀和/积的预计算可能是有用的。例子:除自身数组的乘积最小子数组和LeetCode 问题标注“前缀-和”

作为散列关键字的索引

如果给你一个序列,而面试官要求 O(1)空间,那么可以用这个数组本身作为哈希表。例如,如果数组只有从 1 到 N 的值,其中 N 是数组的长度,则对该索引处的值求反(减一)以指示该数字的存在。例子:第一次不见正每日气温

多次遍历数组

这可能是显而易见的,但是遍历数组两次/三次(只要少于 n 次)仍然是 O(n)。有时多次遍历数组可以帮助您解决问题,同时保持时间复杂度为 O(n)。

基本问题

如果你在学习这个话题,这些是需要练习的基本问题。

推荐练习题

这些是在你为题目学习并练习了基本问题后推荐练习的问题。

推荐课程

AlgoMonsterT3】

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式,并有内容帮助你快速修改基本的数据结构和算法。最重要的是,AlgoMonster 不是基于订阅的——支付一次性费用,就可以获得终身访问今天加入七折优惠→

寻找编码面试:编码问题的模式

设计大师的这门课程扩展了推荐练习题中的问题,但从问题模式的角度来进行练习,这是一种我也同意的学习方法,我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题,并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式,而不是背答案! 现在获得终身使用权→

掌握编码面试:数据结构+算法

这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星,21.5k 评分,135k 学生),包含了价值 19 个小时的内容。像技术面试手册一样,它超越了编码面试,涵盖了简历,非技术面试,谈判。是一个全包!请注意,JavaScript 用于编码演示。 结账→



回到顶部