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

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

本文关键字:数字 范围 有效 方法 范围内 检查      更新时间:2023-09-26

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

  1. n是否在范围内,包括 、 min - max

  2. 数字n包含或不包含重复的数字

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

  4. 上下文:for循环中if的条件,可能需要数千到数十万次迭代才能返回结果;返回trueNumber false检查所需的毫秒可能会影响性能

DevTools Profiles面板上迭代的71,3307项的集合中,下面的RegExp被列为使用总1097.3ms27.2ms来完成循环。在下面迭代的836,7628项的集合中,RegExp使用193.5ms在总共11285.3ms内。

要求:在最短的时间内返回上述参数Boolean truefalse的最有效方法。

注意:解决方案不必限于RegExp;在下面使用,因为模式返回了预期的结果。


当前利用RegExp re jsRegExp.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 
    */
}

关联数组方法:

这样做的优点是易于理解。

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进行比较。
如果您想详细了解这一点,请参阅有关按位运算符的文档。

因此,如果我们要检查 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

解决方案 1

使用正则表达式进行测试

var min = 2;
var max = 7;
res = "";
arr = [81, 35, 22, 45, 49]
arr.push("");
regex=new RegExp("[" + min + "-" + max + "](.)(?!='1)", "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 + "](.)(?!='1)", "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)