JS算法题之查找数字在数组中的索引位置
前言
编写算法时，排序是一个非常重要的概念。它有各种各样的种类：冒泡排序、希尔排序、分块块排序，梳排序，鸡尾酒排序，侏儒排序——这些可不是我瞎编的！
这个算法题能够让我们一睹精彩的世界。我们必须对数字数组进行升序排序，并找出给定数字在该数组中的位置。
算法说明
将值（第二个参数）插入到数组（第一个参数）中，并返回其在排序后的数组中的最低索引。返回的值应该是一个数字。
例如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）。
functiongetIndexToIns(arr,num){
returnnum;
}
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。例如：
letfood=['pizza','icecream','chips','hotdog','cake']
food.indexOf('chips')
//returns2
food.indexOf('spaghetti')
//returns-1
我们将使用.concat()而不是.push()。为什么呢？因为当使用.push()向数组添加元素时，它会返回新数组的长度。而使用.concat()向数组添加元素时，它会返回新数组本身。例如：
letarray=[4,10,20,37,45] array.push(98) //returns6 array.concat(98) //returns[4,10,20,37,45,98]
算法：
- 将num插入arr。
- 将arr进行升序排序。
- 返回num的索引。
代码：
functiongetIndexToIns(arr,num){
//Insertnumintoarr,creatinganewarray.
letnewArray=arr.concat(num)
//[40,60].concat(50)
//[40,60,50]
//Sortthenewarrayfromleasttogreatest.
newArray.sort((a,b)=>a-b)
//[40,60,50].sort((a,b)=>a-b)
//[40,50,60]
//Returntheindexofnumwhichisnow
//inthecorrectplaceinthenewarray.
returnnewArray.indexOf(num);
//return[40,50,60].indexOf(50)
//1
}
getIndexToIns([40,60],50);
去掉局部变量和注释后的代码：
functiongetIndexToIns(arr,num){
returnarr.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，这表示没有元素通过测试。例如：
letnumbers=[3,17,94,15,20] numbers.findIndex((currentNum)=>currentNum%2==0) //returns2 numbers.findIndex((currentNum)=>currentNum>100) //returns-1
这对我们很有用，因为我们可以用.findIndex()将输入num与输入arr中的每个数字进行比较，并找出它从最小到最大的顺序。
算法：
- 如果arr是一个空数组，则返回0。
- 如果num处于排序后数组的末尾，则返回arr的长度。
- 否则，返回索引num。
代码：
functiongetIndexToIns(arr,num){
//Sortarrfromleasttogreatest.
letsortedArray=arr.sort((a,b)=>a-b)
//[40,60].sort((a,b)=>a-b)
//[40,60]
//ComparenumtoeachnumberinsortedArray
//andfindtheindexwherenumislessthanorequalto
//anumberinsortedArray.
letindex=sortedArray.findIndex((currentNum)=>num<=currentNum)
//[40,60].findIndex(40=>50<=40)-->falsy
//[40,60].findIndex(60=>50<=60)-->truthy
//returns1becausenumwouldfitlikeso[40,50,60]
//Returnthecorrectindexofnum.
//IfnumbelongsattheendofsortedArrayorifarrisempty
//returnthelengthofarr.
returnindex===-1?arr.length:index
}
getIndexToIns([40,60],50);
去掉局部变量和注释的代码：
functiongetIndexToIns(arr,num){
letindex=arr.sort((a,b)=>a-b).findIndex((currentNum)=>num<=currentNum)
returnindex===-1?arr.length:index
}
getIndexToIns([40,60],50);
如果你有其他解决方案或建议，请在评论中分享！
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对毛票票的支持。