翻译:疯狂的技术宅
来源:freecodecamp
Photo by Claudel Rheault on Unsplash
编写算法时,排序是一个非常重要的概念。它有各种各样的种类:冒泡排序、希尔排序、分块排序,梳排序,鸡尾酒排序,侏儒排序 —— 这些可不是我瞎编的!【https://en.wikipedia.org/wiki/Sorting_algorithm】
这个算法题能够让我们一睹精彩的世界。我们必须对数字数组进行升序排序,并找出给定数字在该数组中的位置。
将值(第二个参数)插入到数组(第一个参数)中,并返回其在排序后的数组中的最低索引。返回的值应该是一个数字。 例如
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)。
1function getIndexToIns(arr, num) {
2 return num;
3}
4
5getIndexToIns([40, 60], 50);
本算法题原题:https://learn.freecodecamp.org/javascript-algorithms-and-data-structures/basic-algorithm-scripting/where-do-i-belong/
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
.理解问题:有两个输入:一个数组和一个数字。我们的目标是将输入的数字在输入数组后中排序后,再返回它的索引。 示例/测试用例:我们不知道输入的数组是以哪种方式排序的,但是提供的测试用例清楚地表明,输入的数组应该从小到大进行排序。
请注意,在最后一个测试用例中存在边界问题,其中输入数组是一个空数组。
数据结构:由于我们最终将会返回索引,因此应该坚持使用数组。
我们将会用一个名为 .indexOf()
的方法:
.indexOf()
返回元素在数组中出现的第一个索引,如果元素根本不存在则返回 -1
。例如:
1let food = ['pizza', 'ice cream', 'chips', 'hot dog', 'cake']
2food.indexOf('chips')
3// returns 2
4food.indexOf('spaghetti')
5// returns -1
我们将使用 .concat()
而不是 .push()
。为什么呢?因为当使用 .push()
向数组添加元素时,它会返回新数组的长度。而使用 .concat()
向数组添加元素时,它会返回新数组本身。例如:
1let array = [4, 10, 20, 37, 45]
2array.push(98)
3// returns 6
4array.concat(98)
5// returns [4, 10, 20, 37, 45, 98]
算法:
num
插入 arr
。arr
进行升序排序。num
的索引。代码:
1function getIndexToIns(arr, num) {
2 // Insert num into arr, creating a new array.
3 let newArray = arr.concat(num)
4 // [40, 60].concat(50)
5 // [40, 60, 50]
6
7 // Sort the new array from least to greatest.
8 newArray.sort((a, b) => a - b)
9 // [40, 60, 50].sort((a, b) => a - b)
10 // [40, 50, 60]
11
12 // Return the index of num which is now
13 // in the correct place in the new array.
14 return newArray.indexOf(num);
15 // return [40, 50, 60].indexOf(50)
16 // 1
17}
18
19getIndexToIns([40, 60], 50);
去掉局部变量和注释后的代码:
1function getIndexToIns(arr, num) {
2 return arr.concat(num).sort((a, b) => a - b).indexOf(num);
3}
4
5getIndexToIns([40, 60], 50);
理解问题:有两个输入:一个数组和一个数字。我们的目标是将输入的数字在输入数组后中排序后,再返回它的索引。 示例/测试用例:我们不知道输入的数组是以哪种方式排序的,但是提供的测试用例清楚地表明,输入的数组应该从小到大进行排序。
这个解决方案需要考虑两个边界情况:
0
,因为 num
将是该数组中的唯一元素,所以它在索引为 0
的位置。num
的位置处于升序排序后的 arr
的末尾,那么我们需要返回 arr
的长度。数据结构:由于我们最终将会返回索引,因此应该坚持使用数组。
让我们看看.findIndex()
并了解它将如何帮助解决这一挑战:
.findIndex()
返回数组中第一个满足条件的元素索引。否则它将返回 -1
,这表示没有元素通过测试。例如:
1let numbers = [3, 17, 94, 15, 20]
2numbers.findIndex((currentNum) => currentNum % 2 == 0)
3// returns 2
4numbers.findIndex((currentNum) => currentNum > 100)
5// returns -1
这对我们很有用,因为我们可以用 .findIndex()
将输入 num
与输入 arr
中的每个数字进行比较,并找出它从最小到最大的顺序。
算法:
arr
是一个空数组,则返回 0
。num
处于排序后数组的末尾,则返回 arr
的长度。num
。代码:
1function getIndexToIns(arr, num) {
2 // Sort arr from least to greatest.
3 let sortedArray = arr.sort((a, b) => a - b)
4 // [40, 60].sort((a, b) => a - b)
5 // [40, 60]
6
7 // Compare num to each number in sortedArray
8 // and find the index where num is less than or equal to
9 // a number in sortedArray.
10 let index = sortedArray.findIndex((currentNum) => num <= currentNum)
11 // [40, 60].findIndex(40 => 50 <= 40) --> falsy
12 // [40, 60].findIndex(60 => 50 <= 60) --> truthy
13 // returns 1 because num would fit like so [40, 50, 60]
14
15 // Return the correct index of num.
16 // If num belongs at the end of sortedArray or if arr is empty
17 // return the length of arr.
18 return index === -1 ? arr.length : index
19}
20
21getIndexToIns([40, 60], 50);
去掉局部变量和注释的代码:
1function getIndexToIns(arr, num) {
2 let index = arr.sort((a, b) => a - b).findIndex((currentNum) => num <= currentNum)
3 return index === -1 ? arr.length : index
4}
5
6getIndexToIns([40, 60], 50);
如果你有其他解决方案或建议,请在评论中分享!
原文:https://medium.freecodecamp.org/how-to-find-the-index-where-a-number-belongs-in-an-array-in-javascript-9af8453a39a8