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

Question

给定一个数 n ，最小数 min ，最大数 max ，确定

的最有效方法是什么

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

在 DevTools 的 Profiles 面板上迭代了 71,3307 项的集合，下面的 RegExp 被列为使用 27.2ms 共 [=30] =] 完成循环。在 836,7628 项的集合中，在下面迭代 RegExp 使用了 193.5ms，总共 11285.3ms。

要求：最有效的方法 return Boolean true 或 false 在最短的时间内给定上述参数。

注意：解决方案不必限于RegExp；下面用作模式 returned 预期结果。

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

var min = 2
, max = 7
, re = new RegExp("[" + min + "-" + max + "](.)(?!=)", "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 且所有其他位设置为 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

Answer 2

解决方案 1

使用正则表达式测试

var min = 2;
var max = 7;
res = "";
arr = [81, 35, 22, 45, 49]
arr.push("");
regex=new RegExp("[" + min + "-" + max + "](.)(?!=)", "g")
var result = arr.reduce(function(a, b) {
  if (regex.test(a)) {
    res = res + a + " is true\n"
  } else {
    res = res + a + " is false\n"
  };
  return b
});
console.log(res)

reduce 方法在某种意义上是不同的，它类似于 python 中的生成器函数（即时生成输出）

它只是使用回调函数循环遍历数组中的每个元素。我不能说 reduce 函数的效率如何。

然而考虑数组中的两个元素

81                             35          
^
take this value            take the result
and do something           from the previous 
                           element and add it
                           to the result computed
                           for this element

更多信息https://msdn.microsoft.com/en-us/library/ff679975%28v=vs.94%29.aspx

解决方案 2

使用列表存储值及其布尔值

var min = 2;
var max = 7;
res = [""];
arr = [81, 35, 22, 45, 49]
arr.push("");
regex=new RegExp("[" + min + "-" + max + "](.)(?!=)", "g")
var result = arr.reduce(function(a, b) {
  if (regex.test(a)) {
    res.push([a,true])
  } else {
    res.push([a,false])
  };
  return b
});
console.log(res)

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

Most efficient method to check for range of numbers within number without duplicates

javascript

algorithm

numbers

关联数组方法：

二进制掩码方法：

二进制掩码方法的解释：