检查数字范围内没有重复项的数字范围的最有效方法
Most efficient method to check for range of numbers within number without duplicates
给定一个数n
,最小数min
,最大数max
,什么是最有效的方法来确定
-
数
n
是否在范围内,包括 、min
-max
-
数字
n
包含或不包含重复的数字 -
这里的效率意味着该方法或方法集需要最少的计算资源,并在最短的时间内返回
true
或false
-
上下文:
for
循环中if
的条件,可能需要数千到数十万次迭代才能返回结果;返回true
或Number
false
检查所需的毫秒可能会影响性能
在DevTools
Profiles
面板上迭代的71,3307
项的集合中,下面的RegExp
被列为使用总1097.3ms
的27.2ms
来完成循环。在下面迭代的836,7628
项的集合中,RegExp
使用193.5ms
在总共11285.3ms
内。
要求:在最短的时间内返回上述参数Boolean
true
或false
的最有效方法。
注意:解决方案不必限于RegExp
;在下面使用,因为模式返回了预期的结果。
当前利用RegExp
re
js
,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
*/
}
关联数组方法:
这样做的优点是易于理解。
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)
- 需要将变量设置为特定的数字范围
- 用于验证数字范围的正则表达式
- Javascript/Jquery:使用数字范围验证输入
- 创建使用用户输入的数字范围生成的随机数.(JavaScript)
- 需要Javascript数学表达式或公式来将数字范围放在组中
- Javascript / jQuery - 将一个数字范围映射到另一个数字范围
- 始终在 3K 数字范围内选择不同的数字
- Javascript:在数字范围之间转换,保持正确的比例
- 如何在其他重叠的数字范围之间找到可用的数字范围
- 检查数字范围内没有重复项的数字范围的最有效方法
- 在javascript中选择数字范围的算法
- 输入-限制数字范围
- 6位base36数字范围的正则表达式
- 在数字范围内查找空白
- 纯javascript html 5文本类型数字范围验证
- 正则表达式,用于数字中有空格的数字范围
- HTML表单下拉菜单指定数字范围
- 使用循环javascript的数字范围
- 如何在jquery中使用切换大小写(数字范围)
- 构造正则表达式以匹配数字范围