98 - 第n个数字

题目

在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。

注意: n 是正数且在32为整形范围内 ( n < 231)。

示例 1:

输入: 3

输出: 3

示例 2:

输入: 11

输出: 0

说明: 第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。

解答

这题很有趣，中文说是简单题，英文说是中等题

我感觉是一道数学题，或者说是归纳题。。

链接1：https://leetcode-cn.com/problems/nth-digit/solution/shou-xian-zhao-dao-shu-zi-de-wei-zhi-ran-hou-zhao-/

链接2：https://leetcode.com/problems/nth-digit/discuss/88363/Java-solution

var findNthDigit = function (n) {
  let i = 1
  while (n > i * Math.pow(10, i - 1) * 9) {
    n -= i * Math.pow(10, i - 1) * 9
    i++
  }
  let am = Math.floor((n - 1) / i) + Math.pow(10, i - 1)
  a = am.toString()
  if (n % i === 0) {
    return a[i - 1] - '0'
  } else {
    return a[n % i - 1] - "0"
  }
};

Runtime: 56 ms, faster than 48.84% of JavaScript online submissions for Nth Digit.

Memory Usage: 34.1 MB, less than 100.00% of JavaScript online submissions for Nth Digit.

1-9有9个数，10-99有20X9个数，100-999有300X9个数，1000-9999有4000X9个数。以此类推

1. 我们先要确定输入的数字，是在哪个区间里面。方法是不断减每个区间的最大值，直到其小于最大值。

每个区间的标志是i，那么区间最大值是Math.pow(10,i-1)*9，最小值是Math.pow(10,i-1)

1. 然后在该区间里面，确定输入的是第几位数字。

在得到区间中确定的数字，将其变为string型，然后就可以得到确定的数字。

func pow(n int) int {
    ans := 1
    for n != 0 {
        ans *= 10
        n--
    }
    return ans
}
func findNthDigit(n int) int {
    i := 1
    for n > i*pow(i-1)*9 {
        n -= i * pow(i-1) * 9
        i++
    }

    am := (n-1)/i + pow(i-1)
    a := strconv.Itoa(am)
    if n%i == 0 {
        return int(a[i-1] - '0')
    } else {
        return int(a[n%i-1] - '0')
    }
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Nth Digit.

Memory Usage: 1.9 MB, less than 100.00% of Go online submissions for Nth Digit.

class Solution:
    def findNthDigit(self, n: int) -> int:
        i = 1
        while n > i * pow(10, i - 1) * 9:
            n -= i * pow(10, i - 1) * 9
            i += 1
        am = (n - 1) / i + pow(10, i - 1)
        a = str(am)
        if n % i == 0:
            return int(a[i - 1])
        else:
            return int(a[n % i - 1])

Runtime: 36 ms, faster than 64.59% of Python3 online submissions for Nth Digit.

Memory Usage: 13.9 MB, less than 16.67% of Python3 online submissions for Nth Digit.