logo标签列表

按顺序生成数字

javascriptnumbers
3
我希望能够根据输入的位置生成对应的值。例如，如果输入20，则函数应该从0开始生成数字，并按升序继续生成直到创建20个数字，然后输出所生成数字字符串中第20个数字的值（01234567891011121314），即4。
我尝试使用以下代码，但是对于像1,000,000,000这样的大数来说效率并不高：
[...Array(5).keys()];  output => [0, 1, 2, 3, 4]

编辑此帖以澄清，我正在尝试获得更有效的解决方案。

在此，我正在尝试在不到1秒钟的时间内获取较大数值（1,000,000,000）的答案。

我已经有一个解决方案，但它需要超过1秒的时间。

 [...Array(5).keys()].join("")[4]; output => 4
4个回答
2
这是一种不使用数组的简单方法。 

let N = 1000000000, digitsCount = 0, currentNumber = 0;
console.time('Took time: ');
const digits = (x)=>{
    if(x<10)
        return 1;
    if(x<100)
        return 2;
    if(x<1000)
        return 3;
    if(x<10000)
        return 4;
    if(x<100000)
        return 5;
    if(x<1000000)
        return 6;
    if(x<10000000)
        return 7;
    if(x<100000000)
        return 8;
    if(x<1000000000)
        return 9;
    return 10; // Default
}
while(true){
    digitsCount += digits(currentNumber);
    if(digitsCount >= N)
        break;
    currentNumber++;
}
console.timeEnd('Took time: ');
console.log(String(currentNumber)[N-digitsCount+digits(currentNumber)-1])

输出（执行时间可能因个人电脑性能不同而有所不同，但一般在1秒（或1000毫秒）以内）。

Took time: : 487.860ms
9
这仍然需要手动迭代currentNumber ++;从0到所需的位数。它可能可以工作，但就像帖子作者的实现一样，它不是一个非常高效的算法（只是现代计算机可以执行1e9个操作）。 - CertainPerformance
这是一种在空间方面非常高效的算法，因为我没有使用数组来存储数字。尽管时间复杂度仍然是O(n)，但对于作者要求的10^9范围的输入，它在1秒内运行。然而，我同意在时间上更有效的解决方案是在这里使用数学，就像你的答案中所做的那样。 - Ajay Dabas
2

这与钱珀诺恩常数几乎相同。

来自math.stackexchange的一个解决方案是：

enter image description here

（不幸的是，Stack Overflow不支持MathJax）

第一步是找出你在哪个十年。从1位数字有9个数字，从2位数字有180个数字，总共有n⋅9⋅10n−1个n位数字。一旦你找到了这个十年，就可以减去早期十年的数字。所以如果你想要第765个数字，前189个数字来自第一和第二个十年，因此我们想要3位数字中的第576个数字。这将会在第⌈5763⌉=192个数字中出现，即291。由于576≡3(mod3)，所以该数字为1。

程序化地：

const getDigit = (target) => {
  let i = 0;
  let xDigitNumbers = 1; // eg 1 digit numbers, 2 digit numbers
  let digitsSoFar = 1;
  while (true) {
    const digitsThisDecade = xDigitNumbers * 9 * 10 ** (xDigitNumbers - 1);
    if (digitsSoFar + digitsThisDecade > target) {
      // Then this is the "decade" in which the target digit is
      
      // digitIndexThisDecade: eg, starting from '100101102', to find the last '1' in '101', digitIndexThisDecade will be 6
      const digitIndexThisDecade = target - digitsSoFar;
      // numIndexThisDecade: this identifies the index of the number in the decade
      // eg, starting from '100101102', this could be index 2 to correspond to 101 (one-indexed)
      const numIndexThisDecade = Math.floor(digitIndexThisDecade / xDigitNumbers);
      // decadeStartNum: the number right before the decade starts (0, 9, 99, 999)
      const decadeStartNum = 10 ** (xDigitNumbers - 1);
      // num: the number in which the target index lies, eg 101
      const num = decadeStartNum + numIndexThisDecade;
      // digitIndexInNum: the digit index in num that the target is
      // eg, for 101, targeting the last '1' will come from a digitIndexInNum of 2 (zero-indexed)
      const digitIndexInNum = digitIndexThisDecade % xDigitNumbers;
      return String(num)[digitIndexInNum]
    }
    digitsSoFar += digitsThisDecade;
    xDigitNumbers++;
  }
};



for (let i = 0; i < 1000; i++) {
  document.write(`${i}: ${getDigit(i)}<br>`);
}

1
我尝试让变量名字自解释，但如果不够清晰，我会添加更多的注释。这只是实现链接答案中描述的算法。 - CertainPerformance
1
for循环迭代。大量的迭代是昂贵的 - 尝试仅记录调用的结果。 console.log(getDigit(1000000000));（这样它只调用函数一次，而不是调用它并写入数十亿次HTML） - CertainPerformance
1
我使用.join("")将数组转换为字符串'01234567891011121314151617181920'，然后通过索引字符串来访问第N个数字。 

N=20;
console.log ( [...Array(N+1).keys()].join("")[N-1] )     //OUTPUT 4

编辑：我认为有一个解决方案，就是根本不需要创建数组，而是使用数学公式。

引用

是的，这很好，但是当涉及到长数字时，数组方法不够高效并且需要更多时间。 - Mad
2
似乎您忘记添加公式了？ - Nick Parsons
0
在我的解决方案中，我们不需要大量的迭代和循环...但是这个解决方案对于简单理解来说很大...
我为6位数字制作了它，它非常高效...并且可以制作任意数量的数字...甚至可以缩小到小函数，但那样会变得太复杂而难以理解...
所以，给定数字的总数： 对于1位数字，它们是10（0到9）....
对于2位数字，它们是9*10 => 90，总数字 => 90*2 => 180...
对于3位数字，它们是9*10*10 => 900，总数字 => 90*3 => 2700...
对于4位数字，它们是9*10*10*10 => 9000，总数字 => 9000*4 => 36000...
一个用于获取指定位数的总数字的函数。
let totalDigits = n => {
    if (n == 1) return 10;
    return 9 * (10 ** (n - 1)) * n;
}

现在，我们为不同的数字设置一个位置范围， 对于1位数字，它在1到10之间....

对于2位数字，它在11（1 + 10）和190（180 + 10）之间......（10中的1的位置是11，99中第二个9的位置是190）...

对于3位数字，它在191（1 + 10 + 180）和2890（2700 + 180 + 10）之间......以此类推

对于n位数字，获取范围的函数为

//  This function is used to find Range for Positions... Eg : 2 digit Numbers are upto Position 190...(Position 191 is "100" first digit => 1 ) 
let digitN = n => {
    if (n == 1) return totalDigits(1);
    return digitN(n - 1) + totalDigits(n);
}

// To Finally set Ranege for a Given Digit Number... for 1 its [1,10] , for 2 its [11,190]
let positionRange = n => {
    if (n == 1) return [1, 10];
    else return [digitN(n - 1), digitN(n)]
}

所以最终解决方案是

//  This Function tells the total number of digits for the given digit... Eg : there are 10 one digit Numbers , 180 Two Digit Numbers , 2700 3 Digit Numbers
let totalDigits = n => {
    if (n == 1) return 10;
    return 9 * (10 ** (n - 1)) * n;
}

//  This function is used to find Range for Positions... Eg : 2 digit Numbers are upto Position 190...(Position 191 is "100" first digit => 1 ) 
let digitN = n => {
    if (n == 1) return totalDigits(1);
    return digitN(n - 1) + totalDigits(n);
}

// To Finally set Ranege for a Given Digit Number... for 1 its [1,10] , for 2 its [11,190]
let positionRange = n => {
    if (n == 1) return [1, 10];
    else return [digitN(n - 1), digitN(n)]
}

// A simple Hack to get same value for Different Consecutive Numbers , (0.3 or 0.6 or 0.9 or 1 return 1) 
let getDigit = n => {
    if (dataType(n) == "float") {
        n = Math.floor(n);
        n++;
    }
    return n;
}
// To check for Float or Integer Values
function dataType(x) {
    if (Math.round(x) === x) {
        return 'integer';
    }
    return 'float';
}

function f(position) {

    let result, charInd, temp;

    if ((position >= positionRange(1)[0]) && (position <= positionRange(1)[1])) {      //   Positions   1 to 10  (1 Digit Numbers)
        result = position - 1;
        charInd = 0
    }
    if ((position > positionRange(2)[0]) && (position <= positionRange(2)[1])) {      //   Positions   11 to 190 (2 Digit Numbers)
        temp = (position - 10) / 2;
        temp = getDigit(temp);
        result = temp + 9;
        charInd = (position - 11) % 2
    }
    if ((position > positionRange(3)[0]) && (position <= positionRange(3)[1])) {      //   Positions   191 to 2890 (3 Digit Numbers)
        temp = (position - 190) / 3;
        temp = getDigit(temp);
        result = temp + 99;
        charInd = (position - 191) % 3
    }
    if ((position > positionRange(4)[0]) && (position <= positionRange(4)[1])) {      //   Positions   2891 to 38890 (4 Digit Numbers)
        temp = (position - 2890) / 4;
        temp = getDigit(temp);
        result = temp + 999;
        charInd = (position - 2891) % 4
    }
    if ((position > positionRange(5)[0]) && (position <= positionRange(5)[1])) {      //    Positions  38890 to 488890 (5 Digit Numbers)
        temp = (position - 38890) / 5;
        temp = getDigit(temp);
        result = temp + 9999;
        charInd = (position - 38891) % 5
    }
    if ((position > positionRange(6)[0]) && (position <= positionRange(6)[1])) {      //   Positions  488890 to 5888890 (6 Digit Numbers)
        temp = (position - 488890) / 6 ;
        temp = getDigit(temp);
        result = temp + 99999;
        charInd = (position - 488891) % 6
    }
    finalChar = String(result)[charInd];

    console.log("Given Position => ", position, "  Result Number => ", result, "Char Index ==> ", charInd, "Final Char => ", finalChar);
}
let d1 = Date.now();
f(138971); //  Given Position =>  138971   Result Number =>  30016 Char Index ==>  0 Final Char =>  3
let d2 = Date.now();

console.log(d2-d1) ;      //  351
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接