摘要:我们必须对数字数组进行升序排序,并找出给定数字在该数组中的位置。算法说明将值第二个参数插入到数组第一个参数中,并返回其在排序后的数组中的最低索引。我们的目标是将输入的数字在输入数组后中排序后,再返回它的索引。
翻译:疯狂的技术宅
原文:https://medium.freecodecamp.o...
本文首发微信公众号:前端先锋
欢迎关注,每天都给你推送新鲜的前端技术文章
编写算法时,排序是一个非常重要的概念。它有各种各样的种类:冒泡排序、希尔排序、分块块排序,梳排序,鸡尾酒排序,侏儒排序 —— 这些可不是我瞎编的!
这个算法题能够让我们一睹精彩的世界。我们必须对数字数组进行升序排序,并找出给定数字在该数组中的位置。
算法说明将值(第二个参数)插入到数组(第一个参数)中,并返回其在排序后的数组中的最低索引。返回的值应该是一个数字。
例如 getIndexToIns([1,2,3,4], 1.5) 应该返回 1,因为 1.5 大于 1(索引0),但小于 2(索引1)。
同样,getIndexToIns([20,3,5], 19) 应该返回 2,因为数组排序后应该是 [3,5,20] , 19 小于 20 (索引2)且大于 5(索引1)。
function getIndexToIns(arr, num) { return num; } getIndexToIns([40, 60], 50);
本算法题原题
测试用例getIndexToIns([10, 20, 30, 40, 50], 35) 应该返回一个数字 3。
getIndexToIns([10, 20, 30, 40, 50], 30) 应该返回一个数字 2.
getIndexToIns([40, 60], 50) 应该返回一个数字 1.
getIndexToIns([3, 10, 5], 3) 应该返回一个数字 0.
getIndexToIns([5, 3, 20, 3], 5) 应该返回一个数字 2.
getIndexToIns([2, 20, 10], 19) 应该返回一个数字 2.
getIndexToIns([2, 5, 10], 15) 应该返回一个数字 3.
getIndexToIns([], 1) 应该返回一个数字 0.
解决方案#1:.sort(),. indexOf() PEDAC理解问题:有两个输入:一个数组和一个数字。我们的目标是将输入的数字在输入数组后中排序后,再返回它的索引。
示例/测试用例:我们不知道输入的数组是以哪种方式排序的,但是提供的测试用例清楚地表明,输入的数组应该从小到大进行排序。
请注意,在最后一个测试用例中存在边界问题,其中输入数组是一个空数组。
数据结构:由于我们最终将会返回索引,因此应该坚持使用数组。
我们将会用一个名为 .indexOf() 的方法:
.indexOf() 返回元素在数组中出现的第一个索引,如果元素根本不存在则返回 -1。例如:
let food = ["pizza", "ice cream", "chips", "hot dog", "cake"] food.indexOf("chips") // returns 2 food.indexOf("spaghetti") // returns -1
我们将使用 .concat() 而不是 .push()。为什么呢?因为当使用 .push() 向数组添加元素时,它会返回新数组的长度。而使用 .concat() 向数组添加元素时,它会返回新数组本身。例如:
let array = [4, 10, 20, 37, 45] array.push(98) // returns 6 array.concat(98) // returns [4, 10, 20, 37, 45, 98]
算法:
将num 插入 arr。
将 arr 进行升序排序。
返回 num 的索引。
代码:
function getIndexToIns(arr, num) { // Insert num into arr, creating a new array. let newArray = arr.concat(num) // [40, 60].concat(50) // [40, 60, 50] // Sort the new array from least to greatest. newArray.sort((a, b) => a - b) // [40, 60, 50].sort((a, b) => a - b) // [40, 50, 60] // Return the index of num which is now // in the correct place in the new array. return newArray.indexOf(num); // return [40, 50, 60].indexOf(50) // 1 } getIndexToIns([40, 60], 50);
去掉局部变量和注释后的代码:
function getIndexToIns(arr, num) { return arr.concat(num).sort((a, b) => a - b).indexOf(num); } getIndexToIns([40, 60], 50);解决方案#2:.sort(),.findIndex() PEDAC
理解问题:有两个输入:一个数组和一个数字。我们的目标是将输入的数字在输入数组后中排序后,再返回它的索引。
示例/测试用例:我们不知道输入的数组是以哪种方式排序的,但是提供的测试用例清楚地表明,输入的数组应该从小到大进行排序。
这个解决方案需要考虑两个边界情况:
如果输入数组为空,则我们需要返回 0,因为 num 将是该数组中的唯一元素,所以它在索引为 0 的位置。
如果 num 的位置处于升序排序后的 arr 的末尾,那么我们需要返回 arr 的长度。
数据结构:由于我们最终将会返回索引,因此应该坚持使用数组。
让我们看看.findIndex() 并了解它将如何帮助解决这一挑战:
.findIndex() 返回数组中第一个满足条件的元素索引。否则它将返回 -1,这表示没有元素通过测试。例如:
let numbers = [3, 17, 94, 15, 20] numbers.findIndex((currentNum) => currentNum % 2 == 0) // returns 2 numbers.findIndex((currentNum) => currentNum > 100) // returns -1
这对我们很有用,因为我们可以用 .findIndex() 将输入 num 与输入 arr 中的每个数字进行比较,并找出它从最小到最大的顺序。
算法:
如果 arr 是一个空数组,则返回 0。
如果 num 处于排序后数组的末尾,则返回 arr 的长度。
否则,返回索引 num。
代码:
function getIndexToIns(arr, num) { // Sort arr from least to greatest. let sortedArray = arr.sort((a, b) => a - b) // [40, 60].sort((a, b) => a - b) // [40, 60] // Compare num to each number in sortedArray // and find the index where num is less than or equal to // a number in sortedArray. let index = sortedArray.findIndex((currentNum) => num <= currentNum) // [40, 60].findIndex(40 => 50 <= 40) --> falsy // [40, 60].findIndex(60 => 50 <= 60) --> truthy // returns 1 because num would fit like so [40, 50, 60] // Return the correct index of num. // If num belongs at the end of sortedArray or if arr is empty // return the length of arr. return index === -1 ? arr.length : index } getIndexToIns([40, 60], 50);
去掉局部变量和注释的代码:
function getIndexToIns(arr, num) { let index = arr.sort((a, b) => a - b).findIndex((currentNum) => num <= currentNum) return index === -1 ? arr.length : index } getIndexToIns([40, 60], 50);
如果你有其他解决方案或建议,请在评论中分享!
本文首发微信公众号:前端先锋 欢迎扫描二维码关注公众号,每天都给你推送新鲜的前端技术文章 欢迎继续阅读本专栏其它高赞文章:12个令人惊叹的CSS实验项目
必须要会的 50 个React 面试题
世界顶级公司的前端面试都问些什么
11 个最好的 JavaScript 动态效果库
CSS Flexbox 可视化手册
从设计者的角度看 React
过节很无聊?还是用 JavaScript 写一个脑力小游戏吧!
CSS粘性定位是怎样工作的
一步步教你用HTML5 SVG实现动画效果
程序员30岁前月薪达不到30K,该何去何从
14个最好的 JavaScript 数据可视化库
8 个给前端的顶级 VS Code 扩展插件
Node.js 多线程完全指南
把HTML转成PDF的4个方案及实现
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/109504.html
摘要:与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在,至少在被标准化的那一刻起,就支持异步编程了。然而异步编程真正发展壮大,的流行功不可没。在握手过程中,端点交换认证和密钥以建立或恢复安全会话。 1、前端 排序算法总结 排序算法可能是你学编程第一个学习的算法,还记得冒泡吗? 当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较...
摘要:与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在,至少在被标准化的那一刻起,就支持异步编程了。然而异步编程真正发展壮大,的流行功不可没。在握手过程中,端点交换认证和密钥以建立或恢复安全会话。 1、前端 排序算法总结 排序算法可能是你学编程第一个学习的算法,还记得冒泡吗? 当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较...
摘要:与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在,至少在被标准化的那一刻起,就支持异步编程了。然而异步编程真正发展壮大,的流行功不可没。在握手过程中,端点交换认证和密钥以建立或恢复安全会话。 1、前端 排序算法总结 排序算法可能是你学编程第一个学习的算法,还记得冒泡吗? 当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较...
摘要:中的算法附道面试常见算法题解决方法和思路关注每日一道面试题详解面试过程通常从最初的电话面试开始,然后是现场面试,检查编程技能和文化契合度。值得记住的数组方法有和。一个好的解决方案是使用内置的方法。 JavaScript中的算法(附10道面试常见算法题解决方法和思路) 关注github每日一道面试题详解 Introduction 面试过程通常从最初的电话面试开始,然后是现场面试,检查编程...
阅读 796·2021-11-22 11:59
阅读 3179·2021-11-17 09:33
阅读 2276·2021-09-29 09:34
阅读 1910·2021-09-22 15:25
阅读 1896·2019-08-30 15:55
阅读 1296·2019-08-30 15:55
阅读 503·2019-08-30 15:53
阅读 3313·2019-08-29 13:55