最有效的方法来检查数字范围内的数字而不重复 [英] Most efficient method to check for range of numbers within number without duplicates

问题描述

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

Given a number n , a minimum number min , a maximum number max , what is the most efficient method to determine

1. 数字 n 是否在范围内，包括 min - max

1. Number n is or is not within range , inclusive of , min - max

数字 n 是否包含重复的数字

Number n does or does not contain duplicate numbers

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

Efficiency meaning here that the method or set of methods requires the least amount of computational resources and returns either true or false in the least amount of time

上下文：条件如果在 for 循环，可能需要数千到数十万次迭代才能返回结果;返回 true 或 false 所需的毫秒数数字检查可能会影响效果

Context: Condition at if within a for loop which could require from thousands to hundreds of thousands of iterations to return a result; where milliseconds required to return true or false as to Number check could affect performance

个人资料面板 DevTools 关于 71,3307 项目的集合迭代， RegExp 以下被列为使用 27.2ms 的总 1097.3ms 来完成循环。在 836,7628 的集合中迭代 RegExp 以下使用 193.5ms 总计 11285.3ms 。

At Profiles panel at DevTools on a collection of 71,3307 items iterated, RegExp below was listed as using 27.2ms of total 1097.3ms to complete loop . At a collection of 836,7628 items iterated RegExp below used 193.5ms within total of 11285.3ms .

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

Requirement: Most efficient method to return Boolean true or false given above parameters , within the least amount of time.

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

Note: Solution does not have to be limited to RegExp ; used below as the pattern returned expected results.

当前 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 
    */
}

推荐答案

关联数组方法：

这有优势很容易理解。

Associative arrays approach:

This has the advantage of being easily understandable.

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。它应该更快。

This replaces the Array with an integer that is in effect used as an array of bits. It should be faster.

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& （1<<<< d）将由我们的位掩码标记的位与位数（先前标记的位的集合）进行比较。

请参阅按位运算符上的文档如果你想详细了解这一点。

1 << d creates a bit mask, an integer with the d bit set and all other bits set to 0.
digits |= 1 << d sets the bit marked by our bit mask on the integer digits.
digits & (1 << d) compares the bit marked by our bit mask with digits, the collection of previously marked bits.
See the docs on bitwise operators if you want to understand this in detail.

所以，如果我们检查626，我们的数字会是这样的：

So, if we were to check 626, our numbers would go like this:

________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

这篇关于最有效的方法来检查数字范围内的数字而不重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！