一尘不染

检查数字范围内数字范围（无重复）的最有效方法

algorithm

给定一个数字n，一个最小数字min，一个最大数字max，什么是最有效的确定方法

数字n是否在范围内，包括，min-max
数字n不包含重复的数字
效率在这里意味着方法或方法集需要最少的计算资源，并在一个true或false最少的时间内返回
上下文：循环if内的条件for，可能需要进行数千到数十万次迭代才能返回结果；其中毫秒需要返回true或false以Number检查可能会影响性能

在迭代项目集合的Profiles面板DevTools上71,3307，RegExp以下列出了使用27.2mstotal
1097.3ms来完成循环。在以下836,7628 迭代的项目集合中，总计使用了。RegExp``193.5ms``11285.3ms

要求：最有效的方法，可以在最短的时间内返回Boolean true或false给出上述参数。

注意：解决方案并不仅限于RegExp; 在下面用作模式返回预期结果。

当前js利用RegExp re，RegExp.protype.test()

var min = 2

, max = 7

, re = new RegExp("[" + min + "-" + max + "](.)(?!=\1)", "g")

, arr = [81, 35, 22, 45, 49];



for (var i = 0; i < arr.length; i++) {

  console.log(re.test(arr[i]), i, arr[i])

    /*

      false 0 81

      true 1 35

      false 2 22

      true 3 45

      false 4 49

    */

}

阅读 176

2020-07-28

共1个答案

一尘不染

关联数组方法：

这具有易于理解的优点。

function checkDigits(min, max, n) {
    var digits = Array(10);                   // Declare the length of the array (the 10 digits) to avoid any further memory allocation
    while (n) {
        d = (n % 10);                         // Get last digit
        n = n / 10 >>0;                       // Remove it from our number (the >>0 bit is equivalent to compose(Math.floor, Math.abs))
        if (d < min || d > max || digits[d])  // Test if "d" is outside the range or if it has been checked in the "digits" array
            return false;
        else
            digits[d] = true;                 // Mark the digit as existing
    }
}



var min = 2

, max = 7

, arr = [81, 35, 22, 45, 49];



function checkDigits(min, max, n) {

    var digits = Array(10);                   // Declare the length of the array (the 10 digits) to avoid any further memory allocation

    while (n) {

        d = (n % 10);                         // Get last digit

        n = n / 10 >>0;                       // Remove it from our number (the >>0 bit is equivalent to compose(Math.floor, Math.abs))

        if (d < min || d > max || digits[d])  // Test if "d" is outside the range or if it has been checked in the "digits" array

            return false;

        else

            digits[d] = true;                 // Mark the digit as existing

    }

    return true;

}



for (var i = 0; i < arr.length; i++) {

  console.log(checkDigits(min, max, arr[i]), i, arr[i])

}

二进制掩码方法：

这将Array替换为实际上用作位数组的整数。它应该更快。

function checkDigits(min, max, n) {
    var digits = 0;                   
    while (n) {
        d = (n % 10);                         
        n = n / 10 >>0;
        if (d < min || d > max || (digits & (1 << d)))
            return false;
        else
            digits |= 1 << d;
    }
    return true;
}



function checkDigits(min, max, n) {

    var digits = 0;

    while (n) {

        d = (n % 10);

        n = n / 10 >>0;

        if (d < min || d > max || (digits & (1 << d)))

            return false;

        else

            digits |= 1 << d;

    }

    return true;

}

二进制掩码方法的说明：

1 << d创建一个 位掩码 ，一个整数，该d位设置为1，所有其他位设置为0。
digits |= 1 << d在整数上设置由我们的位掩码标记的位digits。
digits & (1 << d)将我们的位掩码标记的位与digits，先前标记的位的集合进行比较。如果您想详细了解这一点，
请参阅按位运算符的文档。

因此，如果我们要检查626，我们的数字将如下所示：

________n_____626_______________
           |
        d  |  6
     mask  |  0001000000
   digits  |  0000000000
           |
________n_____62________________
           |
        d  |  2
     mask  |  0000000100
   digits  |  0001000000
           |
________n_____6_________________
           |
        d  |  6
     mask  |  0001000000
   digits  |  0001000100
                 ^
               bit was already set, return false

2020-07-28