? 进阶算法之“搜索算法”
2022/1/27 17:05:16
本文主要是介绍? 进阶算法之“搜索算法”,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
进阶算法之“搜索算法”
一、理论
1. 排序和搜索简介
- 排序:把某个乱序的数组变成升序或降序数组
- 搜索:找出数组中某个元素的下标
1.1 js中的排序和搜索
- js中的排序:sort()
- js中的搜索:indexOf()
1.2 排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
1.3 搜索算法
- 顺序搜索
- 二分搜索
2. js实现排序
2.1 冒泡排序
2.2.1 思路
- 比较相邻元素,如果第一个比第二个大,则交换他们
- 一轮下来,保证最后一个数是最大的
- 执行n-1轮即完成排序
2.2.2 动画演示
冒泡排序动画演示
2.2.3 coding part
Array.prototype.bubbleSort = function () { for(let i = 0; i < this.length - 1; i++) { for(let j = 0; j < this.length - 1 - i; j++) { if(this[j] > this[j + 1]) { const temp = this[j] this[j] = this[j + 1] this[j + 1] = temp } } } }
2.2.4 时间复杂度
- 时间复杂度:O(n^2)
2.2 选择排序
2.2.1 思路
- 找到数组的最小值,选中并将其放在第一位
- 找到数组的第二小值,选中并将其放在第二位
- 以此类推,执行n-1轮
2.2.2 动画演示
选择排序动画演示
2.2.3 coding part
Array.prototype.selectionSort = function () { for(let i = 0; i < this.length-1; i++) { let indexMin = i for(let j = i; j < this.length; j++) { if(this[j] < this[indexMin]) { indexMin = j } } if(indexMin !== i) { const temp = this[i] this[i] = this[indexMin] this[indexMin] = temp } } }
2.2.4 时间复杂度
- 时间复杂度:O(n^2)
2.3 插入排序
2.3.1 思路
- 从第二个数开始往前比
- 比他大就往后排
- 以此类推进行到最后一个数
2.3.2 动画演示
插入排序动画演示
2.3.3 coding part
Array.prototype.insertionSort = function () { for(let i = 1; i < this.length; i++) { const temp = this[i] let j = i while(j > 0) { if(this[j-1] > temp) { this[j] = this[j-1] } else { break } j-- } this[j] = temp } }
2.3.4 时间复杂度
- 时间复杂度:O(n^2)
2.4 归并排序
2.4.1 思路
- 分:把数组劈成两半,再递归得将子数组进行“分”操作,直到分成一个个单独的数
- 合:把两个数合并为有序数组,再对有序数组进行合并,直到全部子数组合并成一个完整数组
合并两个有序数组
- 新建一个空数组res,用于存放最终排序后的数组
- 比较两个有序数组的头部,较小者出队并推入res中
2.4.2 动画演示
归并排序动画演示
2.4.3 coding part
Array.prototype.mergeSort = function () { const rec = arr => { if(arr.length == 1) return arr const mid = Math.floor(arr.length / 2) const left = arr.slice(0, mid) const right = arr.slice(mid, arr.length) const orderLeft = rec(left) const orderRight = rec(right) const res = [] while(orderLeft.length || orderRight.length) { if(orderLeft.length && orderRight.length) { res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift()) } else if(orderLeft.length) { res.push(orderLeft.shift()) } else if(orderRight.length) { res.push(orderRight.shift()) } } return res } const res = rec(this) res.forEach((n, i) => this[i] = n) }
2.4.4 时间复杂度
- 分的时间复杂度:O(logn)
- 合的时间复杂度:O(n)
- 时间复杂度:O(nlogn)
2.5 快速排序
2.5.1 思路
- 分区:从数组中任意选择一个基准,所有比基准小的元素放在基准前,比基准小的元素放在基准后
- 递归:递归地对基准前后的子数组进行分区
2.5.2 动画演示
快速排序动画演示
2.5.3 coding part
Array.prototype.quickSort = function () { const rec = (arr) => { if(arr.length == 1) return arr const left = [] const right = [] const mid = arr[0]; for(let i = 1; i < this.length; i++) { if(arr[i] < mid) { left.push(arr[i]) } else { right.push(arr[i]) } } return [...rec(left), mid, ...rec(right)] } const res = rec(this) res.forEach((n, i) => this[i] = n) }
2.5.4 时间复杂度
- 递归的时间复杂度:O(logn)
- 分区的时间复杂度:O(n)
- 时间复杂度:O(nlogn)
3. js实现搜索
3.1 顺序搜索
3.1.1 思路
- 遍历数组
- 找到跟目标值相等的元素,返回其下标
- 遍历结束后,若没有找到相等元素则返回-1
3.1.2 coding part
Array.prototype.sequentialSearch = function(item) { for(let i = 0; i < this.length; i++) { if(this[i] === item) { return i } } return -1 }
3.1.3 时间复杂度
- 时间复杂度:O(n)
3.2 二分搜索
前提:数组有序
3.2.1 思路
- 从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束
- 如果目标值大于或小于中间元素,则在大于或小于中间元素的那一半数组中搜索
3.2.2 coding part
Array.prototype.binarySearch = function(item) { let low = 0, high = this.length - 1 while(low <= high) { const mid = Math.floor((low + high) / 2) const element = this[mid] if(element < item) { low = mid + 1 } else if(element > item) { high = mid - 1 } else { return mid } } return -1 }
3.2.3 时间复杂度
- 时间复杂度:O(logn)
二、刷题
1. 合并两个有序链表(21)
1.1 题目描述
- 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
1.2 解题思路
- 与归并排序中合并两个有序数组很相似
- 将数组替换成链表
1.3 解题步骤
- 新建一个新链表,作为返回结果
- 用指针遍历两个有序数组,并比较两个链表当前节点,较小者先接入新链表并将指针后移一步
- 链表遍历结束,返回新链表
function mergeTwoLists(l1, l2) { const res = new ListNode(0); let p = res, p1 = l1, p2 = l2; while(p1 && p2) { if(p1.val < p2.val) { p.next = p1; p1 = p1.next; } else { p.next = p2; p2 = p2.next; } p = p.next; } if(p1) { p.next = p1; } if(p2) { p.next = p2 } return res.next }
1.4 时间复杂度&空间复杂度
- 时间复杂度:O(n)
- 空间复杂度:O(1)
2. 猜数字大小(374)
2.1 题目描述
- 猜数字游戏的规则如下:
- 每轮游戏,我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
- 如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。
- 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果,返回值一共有 3 种可能的情况(-1,1 或 0):
- -1:我的数字比较小 pick < num
- 1:我的数字比较大 pick > num
- 0:恭喜!你猜对了!pick == num
2.2 解题思路
输入:n = 10, pick = 6
输出:6
- 二分搜索
- 调用guess函数来判断中间元素是否是目标值
2.3 解题步骤
- 二分搜索
function guessNumber(n) { let low = 1, high = n; while(low <= high) { const mid = Math.floor((low + high) / 2); const res = guess(mid) if(res === 0) { return mid } else if(res === 1) { low = mid + 1 } else if(res === -1) { high = mid - 1 } } }
2.4 时间复杂度&空间复杂度
- 时间复杂度:O(logn)
- 空间复杂度:O(1)
三、总结 -- 技术要点
这篇关于? 进阶算法之“搜索算法”的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)