美团-零售-秋招 · 第 1 轮 · 一面
← 已是第一轮 · 返回本次面经 · 已是最后一轮 → 本轮要点: 本次面试主要考察前端基础知识,包括数据结构、网络协议、操作系统、JavaScript、CSS、React以及算法等方面。 本轮共 12 道题。答案默认折叠,便于先自行作答。 1. 数组和链表的区别,读取 和 删除 的时间复杂度 题目要点 数据结构基础:考察对数组和链表这两种基本数据结构概念的理解,包括它们的存储方式和特点。 时间复杂度分析:评估数据结构在不同操作下的性能表现,这是衡量算法效率的关键指标。 参考答案 1.1 原理说明 数组:数组是一种将元素存储在连续内存空间中的数据结构。它通过索引来直接访问任意元素,因为所有元素的大小相同且物理地址连续,可以通过首地址和索引计算出元素的确切位置。 链表:链表是一种将元素存储在非连续内存空间中的数据结构。每个元素(称为节点)包含数据本身以及指向下一个元素的指针(或引用)。节点之间通过这些指针逻辑上连接起来,但不要求物理上连续。 联系与区别:数组和链表都是线性数据结构,用于有序地存储和组织数据。它们的主要区别在于内存的物理存储方式和由此带来的对元素访问、插入、删除操作的效率差异。数组支持随机访问,而链表只能顺序访问。 为什么会出现这个技术需求或问题:不同的数据存储和操作场景对数据结构有不同的性能要求。当需要快速随机访问数据时,数组由于其连续存储特性表现更优;而当需要频繁地进行插入和删除操作时,链表由于其灵活的指针连接方式,避免了大量元素移动,因此效率更高。 1.2 核心用法 + 示例代码 读取操作: 数组:通过索引直接访问元素,时间复杂度为 O(1)。无论数组大小,访问任何元素所需时间都是恒定的。 const arr = [10, 20, 30, 40, 50]; console.log(arr[2]); // 输出 30,直接访问,时间复杂度 O(1) 链表:必须从链表的头部节点开始,沿着指针逐个遍历,直到找到目标元素。因此,时间复杂度为 O(n),其中 n 是链表的长度。在最坏情况下,需要遍历整个链表。 class Node { constructor(val) { this.val = val; this.next = null; } } const head = new Node(10); head.next = new Node(20); head.next.next = new Node(30); let current = head; while (current && current.val !== 30) { current = current.next; } console.log(current ? current.val : 'Not found'); // 输出 30,需要遍历,时间复杂度 O(n) 删除操作: 数组:删除数组中的某个元素后,为了保持内存的连续性,其后的所有元素都需要向前移动以填补空缺。这个移动操作的时间复杂度为 O(n)。 const arr = [1, 2, 3, 4, 5]; arr.splice(2, 1); // 删除索引为2的元素(即3),后续元素(4, 5)前移,时间复杂度 O(n) console.log(arr); // 输出 [1, 2, 4, 5] 链表:如果已知要删除节点的前一个节点,删除操作只需要修改前一个节点的指针,使其指向被删除节点的下一个节点。这个操作的时间复杂度为 O(1)。如果需要先查找再删除,则总时间复杂度为 O(n)(查找的开销)。 // 假设我们有一个链表 1 -> 2 -> 3,我们要删除值为 2 的节点 // 模拟找到值为 1 的节点 (prevNode) 和值为 2 的节点 (nodeToDelete) let headDelete = new Node(1); let node2 = new Node(2); let node3 = new Node(3); headDelete.next = node2; node2.next = node3; let prevNode = headDelete; // 值为 1 的节点 let nodeToDelete = node2; // 值为 2 的节点 prevNode.next = nodeToDelete.next; // 将 1 的 next 指向 3,时间复杂度 O(1) // 现在链表变为 1 -> 3 优势总结: ...