内容简介:翻译:疯狂的技术宅原文:本文首发微信公众号:前端先锋
翻译:疯狂的技术宅
原文: 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);
如果你有其他解决方案或建议,请在评论中分享!
本文首发微信公众号:前端先锋
欢迎扫描二维码关注公众号,每天都给你推送新鲜的前端技术文章
欢迎继续阅读本专栏其它高赞文章:
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 菜鸡的算法修炼:数组(旋转数组的最小数字)
- 算法-计算小数组在大数组中的索引
- 数组查询算法(JavaScript)
- JavaScript数组-排序算法
- 算法面试:数组编码面试问题
- 数据结构与算法: 数组
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
MATLAB智能算法30个案例分析
史峰、王辉、胡斐、郁磊 / 北京航空航天大学出版社 / 2011-7-1 / 39.00元
MATLAB智能算法30个案例分析,ISBN:9787512403512,作者:史峰,王辉 等编著一起来看看 《MATLAB智能算法30个案例分析》 这本书的介绍吧!
Markdown 在线编辑器
Markdown 在线编辑器
HEX HSV 转换工具
HEX HSV 互换工具