检查大数组中所有数字相等的最佳方法是什么?

Question

以下方法适用于少量数组，但当我尝试大容量时，它会超时。检查大容量数组中所有数字相等的最佳方法是什么?

在下面的示例中，我正在确认哪些数字在给定数字之间是均匀的，其中它适用于小容量(即1 - 300)，但不适用于大容量(即1 - 999999999999)

引用:

• 检查数组的所有值是否相等
• 检查数组中的每一项在JavaScript中是否相同

使用第一种

const uniformInteger = (A, B) => {
let output = 0;
for (let i = A; i <= B; i++) {
const reversed = i.toString().split("").reverse();
// Option - 1 = using .every
if (reversed.every((val, i, arr) => val === arr[0])) {
output++;
}
}
return output;
};
console.log(uniformInteger(1, 300));
// Timed out
// console.log(uniformInteger(1, 999999999999));

使用设置

const uniformInteger = (A, B) => {
let output = 0;
for (let i = A; i <= B; i++) {
const reversed = i.toString().split("").reverse();
// Option - 2 = using Set
if (new Set(reversed).size == 1) {
output++;
}
}
return output;
};
console.log(uniformInteger(1, 300));

使用另一个循环来检查当前值和下一个值

function identical(array) {
for (var i = 0; i < array.length - 1; i++) {
if (array[i] !== array[i + 1]) {
return false;
}
}
return true;
}
const uniformInteger = (A, B) => {
let output = 0;
for (let i = A; i <= B; i++) {
const reversed = i.toString().split("").reverse();
// Option - 3 = another loop to check current and next value
if (identical(reversed)) {
output++;
}
}
return output;
};
console.log(uniformInteger(1, 300));

Answer 1

如果只是计算一定范围内有多少数字的位数相等，就没有必要检查数十亿个永远不满足条件的数字。优化通常不是使现有的方法更快，而是检查是否有更好的方法来计算结果。

因为例如，如果你已经达到了111111111111，下一个满足你条件的数字将是222222222222。不需要检查111111111112,111111111113,111111111114…

但是你可以很容易地计算出计数，因为对于每个"长度"对于一个数字(即15,10,100,1000，....)，有确切的9数字满足您的条件(即1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,111,222,333…)

因此对于区间[1, B]，其中B = 99999....，满足条件的数的计数为

ceil(log_10(B)) * 9

例如，如果B == 999，它将是

ceil(log_10(999)) * 9 = ceil(2.99...) * 9 = 3 * 9 = 27
//(ie 1, 2, 3, ..., 9, 11, 22, 33, ..., 99, 111, 222, 333, ..., 999) 

如果B不包含所有9，则必须检查B中是否有一个数字小于B的第一位。

如果是，则计数为

floor(log_10(B)) * 9 + firstDigit - 1

如果没有，则计数为

floor(log_10(B)) * 9 + firstDigit

实际上，B = 999....的情况也可以用这两个公式来处理。

例如，如果B == 323的计数是

floor(log_10(B)) * 9 + firstDigit - 1 = 2 * 9 + 3 - 1 = 20
//(ie, 1, 2, 3, ..., 9, 11, 22, 33, ..., 99, 111, 222) 

如果B === 343then count是

floor(log_10(B)) * 9 + firstDigit = 2 * 9 + 3 = 21
//(ie, 1, 2, 3, ..., 9, 11, 22, 33, ..., 99, 111, 222, 333) 

编辑

如果你有一个区间[A,B]其中A != 1最终结果当然是

count(A,B) = count(1,B) - count(1,A - 1) 

我不打算评论你的链接小提琴，因为它们包含了太多的错误，我甚至不知道从哪里开始。所以我只是添加了一个简单直接的实现

function count(a, b) {
if (a > b || a < 1 || b < 1)
return 0;

if (a > 1)
return  count(1, b) - count(1, a - 1);

let 
result = 9 * Math.floor(Math.log10(b)),
smallest = 9,
first = 0
while (b > 0) {
smallest = Math.min(smallest, b % 10)
first = b;
b = Math.floor(b / 10)
}

result += first;
if (smallest < first) result -= 1;
return result;
}

let testinvervals = [
[1,1],
[1, 10],
[1, 1000],
[1, 1234],
[1, 4321],
[2, 9],
[2, 10],
[2, 11],
[11, 99],
[12, 99],
[11, 22],
[33, 33]
]
for (let tv of testinvervals) {
console.log(`[${tv[0]} , ${tv[1]}]`, "-->", count(tv[0], tv[1]))
}