精华内容
下载资源
问答
  • JavaScript专题系列第十篇,讲解如何从数组中查找指定元素,并且跟着 undersocre 实现 findIndex 和 findLastIndex、sortedIndex、indexOf 和 lastIndexOf 前言 开发,我们经常会遇到在数组中查找指定元素的需求...

    JavaScript专题系列第十篇,讲解如何从数组中查找指定元素,并且跟着 undersocre 实现 findIndex 和 findLastIndex、sortedIndex、indexOf 和 lastIndexOf

    前言

    在开发中,我们经常会遇到在数组中查找指定元素的需求,可能大家觉得这个需求过于简单,然而如何优雅的去实现一个 findIndex 和 findLastIndex、indexOf 和 lastIndexOf 方法却是很少人去思考的。本文就带着大家一起参考着 underscore 去实现这些方法。

    在实现前,先看看 ES6 的 findIndex 方法,让大家了解 findIndex 的使用方法。

    findIndex

    ES6 对数组新增了 findIndex 方法,它会返回数组中满足提供的函数的第一个元素的索引,否则返回 -1。

    举个例子:

    function isBigEnough(element) {
      return element >= 15;
    }
    
    [12, 5, 8, 130, 44].findIndex(isBigEnough);  // 3

    findIndex 会找出第一个大于 15 的元素的下标,所以最后返回 3。

    是不是很简单,其实,我们自己去实现一个 findIndex 也很简单。

    实现findIndex

    思路自然很明了,遍历一遍,返回符合要求的值的下标即可。

    function findIndex(array, predicate, context) {
        for (var i = 0; i < array.length; i++) {
            if (predicate.call(context, array[i], i, array)) return i;
        }
        return -1;
    }
    
    console.log(findIndex([1, 2, 3, 4], function(item, i, array){
        if (item == 3) return true;
    })) // 2

    findLastIndex

    findIndex 是正序查找,但正如 indexOf 还有一个对应的 lastIndexOf 方法,我们也想写一个倒序查找的 findLastIndex 函数。实现自然也很简单,只要修改下循环即可。

    function findLastIndex(array, predicate, context) {
        var length = array.length;
        for (var i = length; i >= 0; i--) {
            if (predicate.call(context, array[i], i, array)) return i;
        }
        return -1;
    }
    
    console.log(findLastIndex([1, 2, 3, 4], function(item, index, array){
        if (item == 1) return true;
    })) // 0

    createIndexFinder

    然而问题在于,findIndex 和 findLastIndex 其实有很多重复的部分,如何精简冗余的内容呢?这便是我们要学习的地方,日后面试问到此类问题,也是加分的选项。

    underscore 的思路就是利用传参的不同,返回不同的函数。这个自然是简单,但是如何根据参数的不同,在同一个循环中,实现正序和倒序遍历呢?

    让我们直接模仿 underscore 的实现:

    function createIndexFinder(dir) {
        return function(array, predicate, context) {
    
            var length = array.length;
            var index = dir > 0 ? 0 : length - 1;
    
            for (; index >= 0 && index < length; index += dir) {
                if (predicate.call(context, array[index], index, array)) return index;
            }
    
            return -1;
        }
    }
    
    var findIndex = createIndexFinder(1);
    var findLastIndex = createIndexFinder(-1);

    sortedIndex

    findIndex 和 findLastIndex 的需求算是结束了,但是又来了一个新需求:在一个排好序的数组中找到 value 对应的位置,保证插入数组后,依然保持有序的状态。

    假设该函数命名为 sortedIndex,效果为:

    sortedIndex([10, 20, 30], 25); // 2

    也就是说如果,注意是如果,25 按照此下标插入数组后,数组变成 [10, 20, 25, 30],数组依然是有序的状态。

    那么这个又该如何实现呢?

    既然是有序的数组,那我们就不需要遍历,大可以使用二分查找法,确定值的位置。让我们尝试着去写一版:

    // 第一版
    function sortedIndex(array, obj) {
    
        var low = 0, high = array.length;
    
        while (low < high) {
            var mid = Math.floor((low + high) / 2);
            if (array[mid] < obj) low = mid + 1;
            else high = mid;
        }
    
        return high;
    };
    
    console.log(sortedIndex([10, 20, 30, 40, 50], 35)) // 3

    现在的方法虽然能用,但通用性不够,比如我们希望能处理这样的情况:

    // stooges 配角 比如 三个臭皮匠 The Three Stooges
    var stooges = [{name: 'stooge1', age: 10}, {name: 'stooge2', age: 30}];
    
    var result = sortedIndex(stooges, {name: 'stooge3', age: 20}, function(stooge){
        return stooge.age
    });
    
    console.log(result) // 1

    所以我们还需要再加上一个参数 iteratee 函数对数组的每一个元素进行处理,一般这个时候,还会涉及到 this 指向的问题,所以我们再传一个 context 来让我们可以指定 this,那么这样一个函数又该如何写呢?

    // 第二版
    function cb(fn, context) {
        return function(obj) {
            return fn ? fn.call(context, obj) : obj;
        }
    }
    
    function sortedIndex(array, obj, iteratee, context) {
    
        iteratee = cb(iteratee, context)
    
        var low = 0, high = array.length;
        while (low < high) {
            var mid = Math.floor((low + high) / 2);
            if (iteratee(array[mid]) < iteratee(obj)) low = mid + 1;
            else high = mid;
        }
        return high;
    };

    indexOf

    sortedIndex 也完成了,现在我们尝试着去写一个 indexOf 和 lastIndexOf 函数,学习 findIndex 和 FindLastIndex 的方式,我们写一版:

    // 第一版
    function createIndexOfFinder(dir) {
        return function(array, item){
            var length = array.length;
            var index = dir > 0 ? 0 : length - 1;
            for (; index >= 0 && index < length; index += dir) {
                if (array[index] === item) return index;
            }
            return -1;
        }
    }
    
    var indexOf = createIndexOfFinder(1);
    var lastIndexOf = createIndexOfFinder(-1);
    
    var result = indexOf([1, 2, 3, 4, 5], 2);
    
    console.log(result) // 1

    fromIndex

    但是即使是数组的 indexOf 方法也可以多传递一个参数 fromIndex,从 MDN 中看到 fromIndex 的讲究可有点多:

    设定开始查找的位置。如果该索引值大于或等于数组长度,意味着不会在数组里查找,返回 -1。如果参数中提供的索引值是一个负值,则将其作为数组末尾的一个抵消,即 -1 表示从最后一个元素开始查找,-2 表示从倒数第二个元素开始查找 ,以此类推。 注意:如果参数中提供的索引值是一个负值,仍然从前向后查询数组。如果抵消后的索引值仍小于 0,则整个数组都将会被查询。其默认值为 0。

    再看看 lastIndexOf 的 fromIndex:

    从此位置开始逆向查找。默认为数组的长度减 1,即整个数组都被查找。如果该值大于或等于数组的长度,则整个数组会被查找。如果为负值,将其视为从数组末尾向前的偏移。即使该值为负,数组仍然会被从后向前查找。如果该值为负时,其绝对值大于数组长度,则方法返回 -1,即数组不会被查找。

    按照这么多的规则,我们尝试着去写第二版:

    // 第二版
    function createIndexOfFinder(dir) {
    
        return function(array, item, idx){
            var length = array.length;
            var i = 0;
    
            if (typeof idx == "number") {
                if (dir > 0) {
                    i = idx >= 0 ? idx : Math.max(length + idx, 0);
                }
                else {
                    length = idx >= 0 ? Math.min(idx + 1, length) : idx + length + 1;
                }
            }
    
            for (idx = dir > 0 ? i : length - 1; idx >= 0 && idx < length; idx += dir) {
                if (array[idx] === item) return idx;
            }
            return -1;
        }
    }
    
    var indexOf = createIndexOfFinder(1);
    var lastIndexOf = createIndexOfFinder(-1);

    优化

    到此为止,已经很接近原生的 indexOf 函数了,但是 underscore 在此基础上还做了两点优化。

    第一个优化是支持查找 NaN。

    因为 NaN 不全等于 NaN,所以原生的 indexOf 并不能找出 NaN 的下标。

    [1, NaN].indexOf(NaN) // -1

    那么我们该如何实现这个功能呢?

    就是从数组中找到符合条件的值的下标嘛,不就是我们最一开始写的 findIndex 吗?

    我们来写一下:

    // 第三版
    function createIndexOfFinder(dir, predicate) {
    
        return function(array, item, idx){
    
            if () { ... }
    
            // 判断元素是否是 NaN
            if (item !== item) {
                // 在截取好的数组中查找第一个满足isNaN函数的元素的下标
                idx = predicate(array.slice(i, length), isNaN)
                return idx >= 0 ? idx + i: -1;
            }
    
            for () { ... }
        }
    }
    
    var indexOf = createIndexOfFinder(1, findIndex);
    var lastIndexOf = createIndexOfFinder(-1, findLastIndex);

    第二个优化是支持对有序的数组进行更快的二分查找。

    如果 indexOf 第三个参数不传开始搜索的下标值,而是一个布尔值 true,就认为数组是一个排好序的数组,这时候,就会采用更快的二分法进行查找,这个时候,可以利用我们写的 sortedIndex 函数。

    在这里直接给最终的源码:

    // 第四版
    function createIndexOfFinder(dir, predicate, sortedIndex) {
    
        return function(array, item, idx){
            var length = array.length;
            var i = 0;
    
            if (typeof idx == "number") {
                if (dir > 0) {
                    i = idx >= 0 ? idx : Math.max(length + idx, 0);
                }
                else {
                    length = idx >= 0 ? Math.min(idx + 1, length) : idx + length + 1;
                }
            }
            else if (sortedIndex && idx && length) {
                idx = sortedIndex(array, item);
                // 如果该插入的位置的值正好等于元素的值,说明是第一个符合要求的值
                return array[idx] === item ? idx : -1;
            }
    
            // 判断是否是 NaN
            if (item !== item) {
                idx = predicate(array.slice(i, length), isNaN)
                return idx >= 0 ? idx + i: -1;
            }
    
            for (idx = dir > 0 ? i : length - 1; idx >= 0 && idx < length; idx += dir) {
                if (array[idx] === item) return idx;
            }
            return -1;
        }
    }
    
    var indexOf = createIndexOfFinder(1, findIndex, sortedIndex);
    var lastIndexOf = createIndexOfFinder(-1, findLastIndex);

    值得注意的是:在 underscore 的实现中,只有 indexOf 是支持有序数组使用二分查找,lastIndexOf 并不支持。

    展开全文
  • JavaScript 专题(九)数组中查找指定元素

    万次阅读 多人点赞 2020-11-12 18:05:23
    上一篇文章,我们了解了数组扁平化的思想,并学习了 lodash 是如何处理数组扁平化的。 这次我们来讨论**在数组中查找元素**时所用的一些方法,并且参考lodash来实现我们自己的工具方法

    JavaScript 专题(九)数组中查找指定元素

    上一篇文章中,我们了解了数组扁平化的思想,并学习了 lodash 是如何处理数组扁平化的。
    这次我们来讨论在数组中查找元素时所用的一些方法,并且参考lodash来实现我们自己的工具方法

    一、findIndex 和 findLastIndex

    1.1 findIndex

    findIndex()方法返回数组中满足提供的测试函数的第一个元素的索引。若没有找到对应元素则返回-1。

    const array1 = [5, 12, 8, 130, 44];
    
    const isLargeNumber = (element) => element > 13;
    
    console.log(array1.findIndex(isLargeNumber));
    // expected output: 3
    

    实现

    Array.prototype.newFindIndex = function(callback) {
      const _arr = this;
      const len = _arr.length;
      for (let i = 0; i < len; i++) {
        if (callback(_arr[i], i, _arr)) {
          return i;
        }
      }
      return -1;
    };
    
    const array1 = [5, 12, 8, 130, 44];
    const isLargeNumber = (element) => element > 13;
    console.log(array1.newFindIndex(isLargeNumber));
    // 3
    

    1.2 findLastIndex

    同样当我们倒叙查找首个满足条件的方法时,可以这样写:

    Array.prototype.newFindlastIndex = function(callback) {
      const _arr = this;
      const len = _arr.length;
      for (let i = len - 1; i >= 0; i--) {
        if (callback(_arr[i], i, _arr)) {
          return i;
        }
      }
      return -1;
    };
    
    const array1 = [5, 12, 8, 130, 44];
    const isLargeNumber = (element) => element > 13;
    console.log(array1.newFindlastIndex(isLargeNumber));
    // 4
    

    上面的代码,和正序查找很相似,仅仅改变遍历的条件。

    1.3 合并 findIndex 和 findLastIndex

    大家可以看到,除了循环的条件不同,两个方法几乎一模一样,参考 lodash,我们将两个方法精简一下

    /**
     * @private
     * @param {Array} array The array to inspect.
     * @param {Function} predicate The function invoked per iteration.
     * @param {boolean} [fromRight] 从右向左查找
     * @returns {number} 返回第一个符合条件元素的下标或-1
     */
    function baseFindIndex(array, predicate, fromRight) {
      const { length } = array;
      let index = fromRight ? length : -1; // 确定下标的边界
    
      while (fromRight ? index-- : ++index < length) {
        // index-- 用于倒序边界
        // ++index 用于正序的边界
        if (predicate(array[index], index, array)) {
          return index;
        }
      }
      return -1;
    }
    

    再来看看它的兄弟——underscore 的思路就是利用传参的不同,返回不同的函数。

    function createIndexFinder(dir) {
      return function(array, predicate, context) {
        const { length } = array;
        var index = dir > 0 ? 0 : length - 1;
    
        for (; index >= 0 && index < length; index += dir) {
          if (predicate.call(context, array[index], index, array)) return index;
        }
        return -1;
      };
    }
    
    var findIndex = createIndexFinder(1);
    var findLastIndex = createIndexFinder(-1);
    

    关于 findIndex 我们就告一段落了~,再来看看新的场景和实现吧!

    在这里插入图片描述

    二、sortIndex

    在一个排好序的数组中找到 value 对应的位置,即保证插入数组后,依然保持有序的状态。

    const arr = [1, 3, 5];
    sortedIndex(arr, 0); // 0
    // 不需要插入arr
    

    那么这个又该如何实现呢?

    2.1 遍历

    遍历大家都能想到,虽然它不一定最优解:

    function sortIndex(array, value) {
      for (let i = 0; i < array.length; i++) {
        if (array[i] > value) {
          return i;
        }
      }
      return array.length;
    }
    

    2.2 二分法

    function sortIndex(array, value) {
      let low = 0,
        high = array.length;
      while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (array[mid] < value) {
          low = mid + 1;
        } else {
          high = mid;
        }
      }
      return high;
    }
    

    三、indexOf 和 lastIndexOf

    • indexOf():返回在数组中可以找到一个给定元素的第一个索引,如果不存在则返回-1。从数组的前面向后查找,从 fromIndex 处开始。
    • lastIndexOf() :返回指定元素在数组中的最后一个的索引,如果不存在则返回-1。从数组的后面向前查找,从 fromIndex 处开始。

    3.1 indexOf 的第一版实现

    function indexOf(array, value) {
      for (let i = 0; i < array.length; i++) {
        if (array[i] === value) {
          return i;
        }
      }
      return -1;
    }
    

    emmmm…在看过 findIndex 和 lastFindIndex 的实现后,indexOf 也要整整齐齐的啊~

    3.2 indexOf 和 lastIndexOf 通用第一版

    通过参数来创建不同的查找方法

    function createIndexOf(dir) {
      return function(array, value) {
        let index = dir > 0 ? 0 : arr.length - 1;
        for (; index >= 0 && index < arr.length; index += dir) {
          if (array[i] === value) {
            return i;
          }
        }
        return -1;
      };
    }
    

    3.3 indexOf 和 lastIndexOf 通用第二版

    这一次,我们允许指定查找位置,我们来看看 fromIndex 的作用:

    设定开始查找的位置。如果该索引值大于或等于数组长度,意味着不会在数组里查找,返回 -1。
    如果参数中提供的索引值是一个负值,则将其作为数组末尾的一个抵消,即 -1 表示从最后一个元素开始查找,-2 表示从倒数第二个元素开始查找 ,以此类推。
    注意:如果参数中提供的索引值是一个负值,仍然从前向后查询数组。如果抵消后的索引值仍小于 0,则整个数组都将会被查询。其默认值为 0。

    function createIndexOf(dir) {
      return function(array, value, fromIndex) {
        // 设定开始查找的位置。如果该索引值大于或等于数组长度,意味着不会在数组里查找,返回 -1。
        let length = array == null ? 0 : array.length;
        let i = 0;
        if (!length) return -1;
        if (fromIndex >= length) return -1;
        if (typeof fromIndex === "number") {
          if (dir > 0) {
            // 正序
            // 起始点>=0,沿用起始点,否则起始点为从后向前数fromIndex
            i = fromIndex >= 0 ? fromIndex : Math.max(length + fromIndex, 0);
          } else {
            // 倒序
            // 起始点>=0,沿用起始点,否则起始点为从后向前数fromIndex
            length =
              fromIndex >= 0
                ? Math.min(fromIndex + 1, length)
                : fromIndex + length + 1;
          }
        }
        // 起始下标
        for (
          fromIndex = dir > 0 ? i : length - 1;
          fromIndex >= 0 && fromIndex < length;
          fromIndex += dir
        ) {
          if (array[fromIndex] === item) return fromIndex;
        }
        return -1;
      };
    }
    

    写到这里我们在数组中查找元素就结束了,自己实现的和loadshunderscore还是有很大区别的,如果大家对上面三节的代码任意有更好的实现,请一定写在留言区哦~

    在这里插入图片描述

    参考

    写在最后

    JavaScript 系列:

    1. 《JavaScript 内功进阶系列》(已完结)
    2. 《JavaScript 专项系列》(持续更新)

    关于我

    • 花名:余光(沉迷 JS,虚心学习中)
    • WX:j565017805

    其他沉淀

    这是文章所在 GitHub 仓库的传送门,如果真的对您有所帮助,希望可以点个 star,这是对我最大的鼓励 ~

    展开全文
  • //删除数组中 uid等于‘2222’的元素,1是长度,表示删除这个,如果大于1,则删除这个和之后的元素 arr.splice(arr.find((obj) => {return obj['uid'] === '2222'}),1); //获取数组中 uid等于‘2222’的元素 let...
    //删除数组中 uid等于‘2222’的元素,1是长度,表示删除这个,如果大于1,则删除这个和之后的元素
    arr.splice(arr.find((obj) => {return obj['uid'] === '2222'}),1);
    
    //获取数组中 uid等于‘2222’的元素
    let obj=arr.find((obj) => {return obj['uid'] === '2222'})

     

    展开全文
  • int search( int list[], int n, int x ){ int i,t=-1; for(i=0;i<n&&t==-1;i++){ if(list[i]==x) t=i; } return t; }
  • 题目:二维数组中每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入一个二维数组和整数,判断二维数组中是否含有该整数,有的话返回该整数的位置,更深一步,如果...

    题目:在二维数组中每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入一个二维数组和整数,判断二维数组中是否含有该整数,有的话返回该整数的位置,更深一步,如果含有该整数并输出该整数的个数。

    首先需要纠正一个概念,二维数组就是二维指针的概念。二维数组具有自动寻址功能,但是二维指针却不可以。详情参考http://blog.csdn.net/liyongbao1988/article/details/7463481

    解决思路:
    1.既然是从数组中查找一个数字,那么就完全遍历这个数组即可。通过两层循环来实现。
    2.因为该二维数组的有序性,所有可以考虑如何快速的找到这个数字:首先想到的就是从第一行第一列开始进行查找,发现所要查找的整数等于当前值就返回,大于当前值则无法进行下一步的判断,所以可以考虑如何利用有序性这一特点。如果能想到从右上角或者是左下角开始进行查找,就会发现查找的快速途径。

    #include <iostream>
    using namespace std;
    
    bool findNum(int arr[][4], int num, int len, int width, int& x, int& y);
    void main()
    {
        int x = 0;
        int y = 0;
        int arr[][4] =
        {
            { 1, 2, 8, 9 },
            { 2, 4, 9, 12 },
            { 4, 7, 10 ,13},
            { 6, 8, 11, 15},
            { 8, 10, 13, 16},
    
        };
        findNum(arr, 16, 4, 5, x, y);
        cout << "x=" << x << endl;
        cout << "y=" << y << endl;  
    }
    
    /*
    para: 
    arr 二维数组
    num 要查找的数字
    len 二维数组的长度
    width 二维数字的宽度
    x,y 要查找数字的坐标
    
    return:返回是否查找成功
    */
    bool findNum_2(int arr[][4], int num, int len, int width, int& x, int& y)
    {
        int i = 0;
        int j = len - 1;
        while (i < width && j > 0)//从右上角开始遍历每一列
        {
            if (arr[i][j] == num)
            {
                x = i;
                y = j;
                return true;
            }
            else if (arr[i][j] > num)
            {
                --j;
            }
            else
            {
                ++i;
            }
        }
        return false;
    }
    展开全文
  • 在js数组中查找特定的元素相信对大家来说再熟悉不过了,但越简单的东西越可能出错,小编最近就犯了这样的错误,所以想着干脆将实现的代码整理下来,方便自己以后需要的时候,或者有需要的朋友们参考学习,下面来一起...
  • js数组中删除指定元素

    千次阅读 2018-11-07 16:53:53
    &lt;script type="text/javascript"&gt; Array.pArray.prototype.indexOf = function(val) { //prototype 给数组添加属性 for (var i = 0; i &lt; this.length; i++) { ...
  • JS遍历从数组中删除指定元素,arr为目标数组,aim为目标项 当每次遍历全部内容需要删除的元素不超过一个时,以下两种方法都可用,虽然结果是正确的,但是还是不推荐使用,因为没有包含数组改变后角标值改变的情况。 ...
  • 利用JavaScript的函数有两种方式 1.jQuery jQuery.inArray( value, array [, fromIndex ] ) value ...要查找的值。...一个数组,通过它来查找。...数组索引值,表示从哪里开始查找。默认值是0...
  • //在数组中查找所有出现的x,并返回一个包含匹配索引的数组 function findall(a,x){ var results=[], len=a.length, pos=0; while(pos&lt;len){ pos=a.indexOf(x,pos); if(pos===-1){//未找到就退出循环...
  • 目前国企等一些单位仍然...下面是ie8浏览器,判断数组中某元素是否存在,和删除数组中指定元素的一段javascript脚本,正好今天做业务代码用到了,顺便做一个简单的笔记,方便后续查找,也希望能帮助有需要的js新手。
  • js数组怎么删除指定元素

    千次阅读 2019-11-13 10:55:46
    js数组js部分非常重要的知识,有时我们有这么个需求js...1、JS数组对象定义一个函数,用于查找指定元素在数组中的位置,也就是索引值,代码如下: 1 2 3 4 5 6 Array....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 57,803
精华内容 23,121
关键字:

js在数组中查找指定元素