系列文章目录
此篇属于前端算法入门系列的第二篇,主要介绍如何分析算法的时间复杂度
和空间复杂度
,以及介绍算法题中涉及到的八大常见数据结构,并且给出相应的JavaScript(TypeScript)实现代码,还罗列其使用场景
,以及相关leetcode题目
。
文章目录
- 系列文章目录
- 前言
- 一、时间&空间复杂度
- 1️⃣ 时间复杂度
- 2️⃣ 空间复杂度
- 二、 八大数据结构的JS实现
- 栈
- 2️⃣ 队列
- 3️⃣ 链表
- 4️⃣ 集合
- 5️⃣ 字典(hash)
- 6️⃣ 树
- 7️⃣ 图
- 8️⃣ 堆
- 总结
前言
文章主要包含以下内容:
⭕️时间&空间复杂度分析介绍
- 时间复杂度分析方法
- 空间复杂度分析方法
❌八大数据结构的S实现
.栈
✌.队列
.链表
.集合
✋.字典
.树
.图
.堆
一、时间&空间复杂度
- 复杂度是数量级(方便记忆、推广),不是具体数字。
- 常见复杂度大小比较:
O(n^2)
>O(nlogn)
>O(n)
>O(logn)
>O(1)
1️⃣ 时间复杂度
常见时间复杂度对应关系:
- O(n^2):2层循环(嵌套循环)
- O(nlogn):快速排序(循环 + 二分)
- O(n):1层循环
- O(logn):二分
2️⃣ 空间复杂度
常见空间复杂度对应关系:
- O(n):传入一个数组,处理过程生成一个新的数组大小与传入数组一致
二、 八大数据结构的JS实现
栈
栈
是一个后进先出
的数据结构,Javascript
中没有栈
。
// 数组实现栈数据结构const stack = [] // 入栈stack.push(0)stack.push(1)stack.push(2) // 出栈const popVal = stack.pop() // popVal 为 2
使用场景
- 场景一:十进制转二进制
- 场景二:有效括号
- 场景三:函数调用堆栈
LeetCode题目
有效括号
二叉树的前序遍历
2️⃣ 队列
队列是一个先进先出
的数据结构。JavaScript
中没有队列,但是可以用Array
实现队列的所有功能该处使用的url网络请求的数据。
// 数组实现队列数据结构const queue = []// 入队stack.push(0)stack.push(1)stack.push(2)// 出队const shiftVal = stack.shift() // shiftVal 为 0
使用场景
- 场景一:日常测核酸排队
- 场景二:JS异步中的任务队列
- 场景三:计算最近请求次数
LeetCode题目
最近的请求次数
3️⃣ 链表
链表是多个元素组成的列表,元素存储不连续,用next 执政连接在一起,JavaScript没有链表,但是可以用Object模拟链表
/** * 定义一个 node 节点 */ interface ILinkListNode{value:numbernext?:ILinkListNode}/** * 定义一个 node 节点 */function createLinkList(arr:number[]):ILinkListNode{const len = arr.lengthif(len==0)throw new Error('arr is Empty')let curNode:ILinkListNode={value:arr[len-1]}if(len === 1)return curNodefor(let i= len - 2 ;i >= 0 ;i--){curNode = {value:arr[i]next:curNode}}return curNode}
使用场景
- 场景一:JS中的原型链
- 场景二:使用链表指针获取 JSON 的节点值
LeetCode题目
删除链表中的节点
反转链表
两数相加
删除排序链表中的重复元素
环形链表
4️⃣ 集合
集合是一个无序且唯一的数据结构。ES6 中有集合:Set
,集合常用操作: 去重
,判断某元素是否在集合中,求交集。
// 去重const arr = [1,1,2,2]const arr2 = [...new Set(arr)]// 判断元素是否在集合中const set = new Set(arr)const has = set.has(3)//false// 求交集const set2 = new Set([2,3])const set3 = new Set([...set].filter(item => set2.has(item)))
使用场景
- 场景一:求交集、差集
LeetCode题目
两个数组的交集
5️⃣ 字典(hash)
字典是一种存储唯一值
的数据结构,但它以键值对的形式存储。ES6
中的字典名为Map
,
// 字典const map = new Map()//增map.set('key1','value1')map.set('key2','value2')//减map.delete('key2')//改map.set('key2','value23')//查map.get('key2')
使用场景
场景:leetcode刷题
LeetCode题目
两个数组的交集
有效括号
两数之和
无重复字符的最长子串
最小覆盖子串
6️⃣ 树
树是一种分层
的数据模型。常见的树包括: DOM、树、级联选择、树形控件…。Javascript中没有树
,但是可以通过Object
和Arrray
构建树。树的常用操作:深度/ 广度优先遍历,先中后序遍历
。
TS实现
/** * 前序遍历:root -> left -> right * 中序遍历:left -> root -> right * 后序遍历:left -> right -> root * 问1:为什么二叉树很重要,而不是三叉树、四叉树? * 答: * (1)数组、链表各有缺点 * (2)特定的二叉树(BBST,平衡二叉树)可以结合数组 & 链表的优点,让整体查找效果最优(可用二分法) * (3)各种高级二叉树(红黑数、B树),继续优化,满足不同场景 * 问2:堆特点?和二叉树的关系? * 答: * (1)逻辑结构是一棵二叉树 * (2)物理结构是一个数组 * (3)数组:连续内存 + 节省空间 * (4)查询比 BST 慢 * (5)增删比 BST 快,维持平衡更快 * (6)整体时间复杂度都在 O(logn) 级别,与树一致 * @description 二叉搜索树 * @author hovinghuang */interface ITreeNode {value: numberleft: ITreeNode | nullright: ITreeNode | null}const treeArr: number[] = []/** * 前序遍历 * @param node* @returns*/function preOrderTraverse(node: ITreeNode | null): void {if (node == null) returnconsole.info(node.value)treeArr.push(node.value)preOrderTraverse(node.left)preOrderTraverse(node.right)}/** * 中序遍历 * @param node* @returns*/function inOrderTraverse(node: ITreeNode | null): void {if (node == null) returninOrderTraverse(node.left)console.info(node.value)treeArr.push(node.value)inOrderTraverse(node.right)}/** * 后序遍历 * @param node* @returns*/function postOrderTraverse(node: ITreeNode | null): void {if (node == null) returnpostOrderTraverse(node.left)postOrderTraverse(node.right)console.info(node.value)treeArr.push(node.value)}function getKthValue(node: ITreeNode, k: number): number | null {inOrderTraverse(bst)return treeArr[k - 1] || null}const bst: ITreeNode = {value: 5,left: {value: 3,left: {value: 2,left: null,right: null},right: {value: 4,left: null,right: null,}},right: {value: 7,left: {value: 6,left: null,right: null},right: {value: 8,left: null,right: null}}}// 功能测试// preOrderTraverse(bst)// inOrderTraverse(bst)// postOrderTraverse(bst)// console.info('第3小值', getKthValue(bst, 3))
使用场景
- 场景一:DOM树
- 场景二:级联选择器
LeetCode题目
- 二叉树的最大深度
- 二叉树的最小深度
- 二叉树的层序遍历
- 二叉树的中序遍历
- 路径总和
7️⃣ 图
图是网络结构
的抽象模型,是一组由边连接的节点。图可以表示任何二元关系,比如道路,航班。JS中没有图,但可以用Object
和Array
构建图。图的表示法:邻接矩阵,邻接表,关联矩阵。
// 邻接表表示图结构const graph={0:[1,2]1:[2]2:[0,3]3:[3]}// 深度优先遍历const visited = new Set()function dfs(n,visited){// n 表示开始访问的根节点console.log(n)visited.add(n)graph[n].forEach((item)=>{if(!visited.has(item))dfs(item,visited)})}dfs(2,visited)//2,0,1,3console.log(visited)//2,0,1,3// 广度优先遍历function bfs(n){const visited= new Set()visited.add(n)const queue = [n]while(queue.length){const shiftVal = queue.shift()graph[shiftVal].forEach((item)=>{if(!visited.has(item)){queue.push(item)visisted.add(item)}})}console.log(visited) // {2, 0, 3, 1}}bfs(2)
使用场景
场景一:道路
场景二:航班
LeetCode题目
有效数字
太平洋大西洋水流问题
克隆图
8️⃣ 堆
堆是一种特殊的完全二叉树
。所有的节点都大于等于(最大堆)或小于等于(最小堆)它的子节点。由于堆的特殊结构,我们可以用数组
表示堆。
1 / \2 3 / \/\45 6// 数组表示堆结构const heap = [1, 2, 3, 4, 5, 6]// 实现一个最小堆类class MinHeap {constructor() {this.heap = [];}swap(i1, i2) {const temp = this.heap[i1];this.heap[i1] = this.heap[i2];this.heap[i2] = temp;}getParentIndex(i) {return (i - 1) >> 1;}getLeftIndex(i) {return i * 2 + 1;}getRightIndex(i) {return i * 2 + 2;}shiftUp(index) {if (index == 0) { return; }const parentIndex = this.getParentIndex(index);if (this.heap[parentIndex] > this.heap[index]) {this.swap(parentIndex, index);this.shiftUp(parentIndex);}}shiftDown(index) {const leftIndex = this.getLeftIndex(index);const rightIndex = this.getRightIndex(index);if (this.heap[leftIndex] < this.heap[index]) {this.swap(leftIndex, index);this.shiftDown(leftIndex);}if (this.heap[rightIndex] < this.heap[index]) {this.swap(rightIndex, index);this.shiftDown(rightIndex);}}insert(value) {this.heap.push(value);this.shiftUp(this.heap.length - 1);}pop() {this.heap[0] = this.heap.pop();this.shiftDown(0);}peek() {return this.heap[0];}size() {return this.heap.length;}}const h = new MinHeap();h.insert(3);h.insert(2);h.insert(1);h.pop();
使用场景
场景:leetcode刷题
LeetCode题目
数组中的第K个最大元素
前 K 个高频元素
合并K个升序链表
总结
您的点赞和评论是我持续更新的动力,感谢关注。
❤️