JavaScript算法练习:将一个数插入数组并返回其索引值

今天在这篇文章要完成的算法练习是:将一个数按照大小顺序插入到一个数组中,并且找出这个数在该数组中的索引值。

任务

将创建一个函数where()并且给这个函数传入两个参数,其中一个参数是数组arr,而另一个参数是num。函数where()要完成的功能是,将参数num按照大小顺序插入到数组arr中,并且找出num在该数组中的索引值。

测试用例

  • where([1,2,3,4], 1.5)将返回1
  • where([20,3,5],19)将返回2
  • where([40,60],50)将返回1

实现思路

实现上述功能,大致思路分为下面几个步骤:

  • 可以通过push()或者unshift(),把参数num放到arr
  • 对数组arr进行排序,在过sort()将数组由小到大做升序排序
  • 使用indexOf()找出num在数组arr中的index(或者使用for循环)
  • 传回index

要将数字num传入数组arr中,简单点的方法,可以通过数组的一些方法,比如Array.prototype.push()方法将一个元素或多个元素添加到一个数组的末尾,或者通过Array.prototype.unshift()方法在数组开头添加一个或者多个元素。

var arr = [40,60];
arr.push(50); // [40,60,50]// 
或者
arr.unshift(50); //[50,40,60]

另外,函数where()另一个功能是要把num放到数组arr中,并且让其由小大到排序。要达到这个效果,那么要将数组进行排序,而数组排序,简单点的方法就是使用Array.prototype.sort()方法。

使用Array.prototype.sort()方法,需要调用一个compare函数,而这个compare函数的主要功能是判断是按升序或降序排列。比如:

function compare(a, b) {
    if (a < b) {
        return -1; // a排在b的前面
    } else if (a > b) {
        return 1; // a排在b的后面
    } else {
        return 0; // a和b的位置保持不变
    }
}

arr.sort(compare); //[40,50,60]

有关于数组排序的详细介绍,可以看看早前整理的一篇文章

最后一步是找出数字num在新数组arr中的索引值。要找出num在数组中的索引值方法有很多种,

  • for或者for ... in循环
  • indexOf()方法
  • parseInt()方法

实现方法

下面整理了一些实现方法,提供大家参考。在看每个实现方案之前,大家注意,如果方法中的sort()方法调用了compare函数的话,在实际使用中应该将下面的函数方法写入进去:

function compare(a, b) {
    if (a < b) {
        return -1; // a排在b的前面
    } else if (a > b) {
        return 1; // a排在b的后面
    } else {
        return 0; // a和b的位置保持不变
    }
}

当然,你也可以直接写成:

arr.sort(function compare (a, b) {
    if (a < b) {
        return -1; // a排在b的前面
    } else if (a > b) {
        return 1; // a排在b的后面
    } else {
        return 0; // a和b的位置保持不变
    }
});

方法1

function where(arr, num) {
    arr.push(num); // arr = [40,60,50]
    arr.sort(compare); // arr = [40,50,60]
    for (var i = 0, len = arr.length; i < len; i++) {
        if (arr[i] === num) {
            return i;
            /*
             *  arr = [40,50,60], len = 3, num = 50
             *  遍历次数   i = ?   i < len  arr[i]   arr[i] === num
             *  1st       0        yes      40       false
             *  2nd       1        yes      50       true
             *  3rd       2        yes      60       false
             *  4th       3        no
             *  end loop
             *  
             */
        }
    }
}

如果需要确定方法对不对,只需要跑一下文章开头提供的测试用例:

where([1,2,3,4], 1.5); // 1
where([20,3,5],19);    // 2
where([40,60],50);     // 1

方法2

function where(arr, num) {
    arr.push(num);
    arr.sort(compare);
    return arr.indexOf(num);
}

方法3

function where(arr, num) {
    arr.sort(compare); // [40,60]
    for (var i in arr) {
        if (arr[i] >= num) {
            return parseInt(i);
        };
    }
    return arr.length;
}

有关于parseInt更多的介绍可以阅读下面的文章:

方法4

function where(arr, num) {
    arr.sort(compare);
    for (var i = 0, len = arr.length; i < len; i++) {
        if (arr[i] >= num) {
            return arr.indexOf(arr[i]);
        }
    }
    return arr.length;
}

方法5

function where(arr, num) {
    arr.sort(compare);
    var count = 0;
    for (var i = 0, len = arr.length; i < len; i++) {
        if (arr[i] < num) {
            count++;
        }
    }
    return count;
}

方法6

function where(arr, num) {
    arr.sort(compare);
    var newArray = [];
    for (var i = 0, len = arr.length; i < len; i++) {
        if (arr[i] < num) {
            newArray.push(arr[i]);
        }
    }
    return newArray.length;
}

方法7(ES6方法)

function where(arr, num) {
    let index = arr.sort((x, y) => x - y).find(x => num <= x);
    return index === undefined ? arr.length : arr.indexOf(index);
}

总结

文章总结了几种不同的方法,用来实现将一个数按照大小顺序插入到一个数组中,并且找出这个数在该数组中的索引值。

原文链接:https://www.w3cplus.com/javascript/bonfire-where-do-i-belong.html

发表评论

登录后才能评论