JavaScript算法题：查找数字在数组中的索引[每日前端夜话0x69]

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}45getIndexToIns([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.

解决方案＃1：`.sort()`，. indexOf`()`

PEDAC

理解问题：有两个输入：一个数组和一个数字。我们的目标是将输入的数字在输入数组后中排序后，再返回它的索引。
示例/测试用例：我们不知道输入的数组是以哪种方式排序的，但是提供的测试用例清楚地表明，输入的数组应该从小到大进行排序。

请注意，在最后一个测试用例中存在边界问题，其中输入数组是一个空数组。

数据结构：由于我们最终将会返回索引，因此应该坚持使用数组。

我们将会用一个名为 .indexOf() 的方法：

.indexOf() 返回元素在数组中出现的第一个索引，如果元素根本不存在则返回 -1。例如：

1let food = ['pizza', 'ice cream', 'chips', 'hot dog', 'cake']2food.indexOf('chips')3// returns 24food.indexOf('spaghetti')5// returns -1

我们将使用 .concat() 而不是 .push()。为什么呢？因为当使用 .push() 向数组添加元素时，它会返回新数组的长度。而使用 .concat() 向数组添加元素时，它会返回新数组本身。例如：

1let array = [4, 10, 20, 37, 45]2array.push(98)3// returns 64array.concat(98)5// returns [4, 10, 20, 37, 45, 98]

算法：

1.将num 插入 arr。

2.将 arr 进行升序排序。

3.返回 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]1112  // Return the index of num which is now13  // in the correct place in the new array.14     return newArray.indexOf(num);15  // return [40, 50, 60].indexOf(50)16  // 117}1819getIndexToIns([40, 60], 50);

去掉局部变量和注释后的代码：

1function getIndexToIns(arr, num) {2  return arr.concat(num).sort((a, b) => a - b).indexOf(num);3}45getIndexToIns([40, 60], 50);

解决方案＃2：`.sort()`，`.findIndex()`

PEDAC

理解问题：有两个输入：一个数组和一个数字。我们的目标是将输入的数字在输入数组后中排序后，再返回它的索引。
示例/测试用例：我们不知道输入的数组是以哪种方式排序的，但是提供的测试用例清楚地表明，输入的数组应该从小到大进行排序。

这个解决方案需要考虑两个边界情况：

1.如果输入数组为空，则我们需要返回 0，因为 num 将是该数组中的唯一元素，所以它在索引为 0 的位置。

2.如果 num 的位置处于升序排序后的 arr 的末尾，那么我们需要返回 arr 的长度。

数据结构：由于我们最终将会返回索引，因此应该坚持使用数组。

让我们看看.findIndex() 并了解它将如何帮助解决这一挑战：

.findIndex() 返回数组中第一个满足条件的元素索引。否则它将返回 -1，这表示没有元素通过测试。例如：

1let numbers = [3, 17, 94, 15, 20]2numbers.findIndex((currentNum) => currentNum % 2 == 0)3// returns 24numbers.findIndex((currentNum) => currentNum > 100)5// returns -1

这对我们很有用，因为我们可以用 .findIndex() 将输入 num 与输入 arr 中的每个数字进行比较，并找出它从最小到最大的顺序。

算法：

1.如果 arr 是一个空数组，则返回 0。

2.如果 num 处于排序后数组的末尾，则返回 arr 的长度。

3.否则，返回索引 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) --> falsy12  //            [40, 60].findIndex(60 => 50 <= 60) --> truthy13  //            returns 1 because num would fit like so [40, 50, 60]1415  // 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 : index19}2021getIndexToIns([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 : index4}56getIndexToIns([40, 60], 50);

如果你有其他解决方案或建议，请在评论中分享！

原文：https://medium.freecodecamp.org/how-to-find-the-index-where-a-number-belongs-in-an-array-in-javascript-9af8453a39a8

算法说明

测试用例

解决方案＃1：`.sort()`，. indexOf`()`

解决方案＃2：`.sort()`，`.findIndex()`

更多相关文章

随机推荐

JavaScript算法题：查找数字在数组中的索引[每日前端夜话0x69]

算法说明

测试用例

解决方案＃1：.sort()，. indexOf()

解决方案＃2：.sort()，.findIndex()

更多相关文章

随机推荐

解决方案＃1：`.sort()`，. indexOf`()`

解决方案＃2：`.sort()`，`.findIndex()`