JavaScript算法题:查找数字在数组中的索引

栏目: 编程工具 · 发布时间: 5年前

内容简介:翻译:疯狂的技术宅原文:本文首发微信公众号:前端先锋

翻译:疯狂的技术宅

原文: 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]

算法:

  1. num 插入 arr
  2. arr 进行升序排序。
  3. 返回 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

理解问题:有两个输入:一个数组和一个数字。我们的目标是将输入的数字在输入数组后中排序后,再返回它的索引。

示例/测试用例:我们不知道输入的数组是以哪种方式排序的,但是提供的测试用例清楚地表明,输入的数组应该从小到大进行排序。

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

  1. 如果输入数组为空,则我们需要返回 0 ,因为 num 将是该数组中的 唯一 元素,所以它在索引为 0 的位置。
  2. 如果 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 中的每个数字进行比较,并找出它从最小到最大的顺序。

算法:

  1. 如果 arr 是一个空数组,则返回 0
  2. 如果 num 处于排序后数组的末尾,则返回 arr 的长度。
  3. 否则,返回索引 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算法题:查找数字在数组中的索引

欢迎继续阅读本专栏其它高赞文章:


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

The Definitive Guide to HTML5 WebSocket

The Definitive Guide to HTML5 WebSocket

Vanessa Wang、Frank Salim、Peter Moskovits / Apress / 2013-3 / USD 26.30

The browser is, hands down, the most popular and ubiquitous deployment platform available to us today: virtually every computer, smartphone, tablet, and just about every other form factor imaginable c......一起来看看 《The Definitive Guide to HTML5 WebSocket》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具