美团-零售-秋招 · 第 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 优势总结： ...