algorithm - Go lang : search x digits from sets of numbers, 为什么需要很长时间才能执行？

Question

我尝试制作从一组数字中找到 x 个数字 的小程序，例如:我想从 中找到 89 个数字strong>1 - 1000000000。

这是我的代码:https://play.golang.org/p/93yh_urX16

package main

import (

    "fmt"
    "strconv"

)

var bucket string

func main() {

    findDigits( 89, 1000000000 )

}

func findDigits( digits int, length int) {

    for i := 1; i <= length; i++ {

        bucket += strconv.Itoa(i)

    }

    fmt.Println( "The", digits, "th digit from 1", "-", length, "is :", string ( [] rune ( bucket )[digits - 1] ) )

}

有谁知道，我犯了什么错误？我需要一些建议来改进这段代码。

谢谢:)

Answer 1

Your program 非常非常低效。 user1431317's program 效率很低。

简单计算一下值。它只需要几纳秒的 CPU 时间和一些内存分配，即使对于像 9,223,372,036,854,775,807 这样大的数字索引(在我的计算机上需要 95.6 纳秒和 2 次分配)。例如，

package main

import (
    "fmt"
    "math"
    "strconv"
)

// digit returns the ith digit from the sequence of
// concatenated non-negative integers.
// The sequence of digits is 01234567891011121314151617181920...
func digit(i int64) string {
    // There are 9 one digit positive integers, 90 two digit,
    // 900 three digit, and so on.
    if i <= 0 {
        return "0"
    }
    j := int64(1)
    w := 1
    for ; ; w++ {
        t := j + 9*int64(math.Pow10(w-1))*int64(w)
        if 0 > t || t > i {
            break
        }
        j = t
    }
    k := i - j
    n := k / int64(w)
    m := k % int64(w)
    d := strconv.FormatInt(int64(math.Pow10(w-1))+n, 10)[m]
    return string(d)
}

func main() {
    tests := []int64{
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
        10, 11, 12, 13,
        88, 89,
        188, 189, 190, 191, 192,
        math.MaxInt32, math.MaxInt64,
    }
    for _, n := range tests {
        fmt.Println(n, digit(n))
    }
}

输出:

0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 1
11 0
12 1
13 1
88 4
89 9
188 9
189 9
190 1
191 0
192 0
2147483647 2
9223372036854775807 9