Ex44 数字序列中某一位数字

题目描述

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

解题思路

这个题的主要思路在于，要将数字分为以下几段：

• 0~9，一位数，共10个数，总位数为10；
• 11～99，两位数，共90个数，总位数180；
• 100～999，三位数，共900个数，总位数1800。

以此类推，得到输入的n落在哪个区间内。然后，将n减去之前的总个数，得到的仍然赋为n，有

• n / digits为这个区间内第几个数；
• n % digits为这个数的倒数第几个数字。

综上，得到要求的数字。

代码

class Solution
{
public:
  int
  findNthDigit (int n)
  {
    int digits = 1;
    while (true)
      {
        long numbers = digits == 1 ? 10 : 9 * (int)std::pow (10, digits - 1);
        if (n < numbers * digits)
          {
            long begin_number
                = digits == 1 ? 0 : (long)std::pow (10, digits - 1);
            int number = begin_number + n / digits;
            int index = digits - n % digits;
            for (int i = 1; i < index; ++i)
              number /= 10;
            return number % 10;
          }
        n -= digits * numbers;
        ++digits;
      }
    return -1;
  }
};

结果

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6.3 MB, 在所有 C++ 提交中击败了20.30%的用户