javascript - 检查数字范围内没有重复的数字范围的最有效方法

Question

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

1. 编号 n是否在范围内，包括 , min - max

2. 编号 n是否包含重复数字

3. 这里的效率意味着方法或方法集需要最少的计算资源并返回 true或 false在最短的时间内

4. 上下文:if 处的条件在 for 内可能需要数千到数十万次迭代才能返回结果的循环；返回所需的毫秒数 true或 false关于Number检查可能会影响性能

在 Profiles面板位于 DevTools关于 71,3307 的集合项目迭代，RegExp下面被列为使用 27.2ms总计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 
    */
}

Answer 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])
}

二元掩码方法:

这会将数组替换为一个整数，该整数实际上用作位数组。它应该更快。

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 的整数位设置，所有其他位设置为 0。
digits |= 1 << d在整数 digits 上设置由我们的位掩码标记的位.
digits & (1 << d)将我们的位掩码标记的位与 digits 进行比较，先前标记位的集合。
请参阅 bitwise operators 上的文档如果您想详细了解这一点。

所以，如果我们要检查 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