javascript - 篝火算法挑战赛: Where Do I Belong on javascript

Question

大家好，我目前在 FCC 上遇到这个算法挑战。这就是挑战的全部内容:

返回排序后应将值(第二个参数)插入数组(第一个参数)的最低索引。返回值应该是一个数字。

例如，getIndexToIns([1,2,3,4], 1.5) 应该返回 1 因为它大于 1 (索引 0)，但小于 2(索引 1)。

同样，getIndexToIns([20,3,5], 19) 应该返回 2 因为一旦数组排序后它看起来像 [3 ,5,20] 和 19 小于 20(索引 2)且大于 5(索引 1)。

这是我的代码:

function getIndexToIns(arr, num) {
    var getIndx;

    var newArr = arr.sort(function (a, b) {
        return (a - b);
    });

    for (i = 0; i < newArr.length; i++) {
        if (num > newArr[i]) {
            getIndx = newArr.indexOf(newArr[i]);
        }
    }

    return getIndx;
}

getIndexToIns([10, 20, 30, 40, 50], 35);

当我运行代码时，它运行正常，但未通过测试。伙计们，我需要你的帮助。谢谢

Answer 1

到目前为止提出的解决方案往往从字面上遵循问题的要求:首先对数组进行排序，然后找到插入数字的索引。这使您遍历数组两次。如果必须克隆阵列，则更多。这是缓慢的，即使不考虑我们最终创造的所有垃圾......

我们可以做得更好吗？我想是的。

如何“计算数组中有多少数字小于或等于要插入的数字”。这实现了相同的目标，但让我们只在数组上循环一次。

function getIndexToIns(arr, num) {
    return arr.reduce(function (c, x) { return x <= num ? c+1 : c }, 0);
}

console.log(getIndexToIns([10, 20, 30, 40, 50], 35)); // 3
console.log(getIndexToIns([20,3,5], 19)); //2 
console.log(getIndexToIns([1,2,3,4], 1.5)); //1
console.log(getIndexToIns([1,2,3,4], 1)); //1
console.log(getIndexToIns([1,2,3,4], 0)); //0

怎么样？快两倍*，耶!

* it's probably not really twice as fast, if you have to be nitpicky about my claims...

编辑

其实我可以做得更好。那个三元 if 在代码中引入了一些困扰我的分支。我们可以利用 javascript 的怪异特性来避免它

arr.reduce(function (c, x) { return c + (x <= num) }, 0)

为什么？因为与数字运算结合使用时，true 转换为 1，false 转换为 0
这从代码中删除了额外的分支，因此它会比以前的版本稍微快一些......如果你关心的话，它也会更容易进行单元测试。