C#LeetCode刷题之#400-第N个数字（Nth Digit）

问题

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

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

输入:3

输出:3

输入:11

输出:0

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

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

Note:n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Input:3

Output:3

Input:11

Output:0

Explanation:The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … is a 0, which is part of the number 10.

示例

public class Program {

    public static void Main(string[] args) {
        var n = 15;
        var res = FindNthDigit(n);
        Console.WriteLine(res);

        n = 38;
        res = FindNthDigit2(n);
        Console.WriteLine(res);

        n = 168;
        res = FindNthDigit3(n);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static int FindNthDigit(int n) {
        //暴力求解，此解法LeetCode超时未AC
        var res = 0;
        var num = 1;
        while(res < n) {
            res += num.ToString().Length;
            num++;
        }
        num--;
        res = int.Parse(num.ToString()
                        [num.ToString().Length - (res - n) - 1].ToString());
        return res;
    }

    private static int FindNthDigit2(int n) {
        int digitType = 1;
        long digitNum = 9;
        //分析n是几位
        while(n > digitNum * digitType) {
            n -= (int)digitNum * digitType;
            digitType++;
            digitNum *= 10;
        }
        //第几个第几位
        int indexInSubRange = (n - 1) / digitType;
        int indexInNum = (n - 1) % digitType;
        //输出结果
        int num = (int)Math.Pow(10, digitType - 1) + indexInSubRange;
        int result = int.Parse(("" + num)[indexInNum] + "");
        return result;
    }

    private static int FindNthDigit3(int n) {
        long start = 1, sz = 1, bace = 9;
        while(sz * bace < n) {
            n -= (int)(sz * bace);
            bace *= 10;
            ++sz;
            start *= 10;
        }
        int target = (int)(start + (n - 1) / sz);
        return target.ToString()[(n - 1) % (int)sz] - '0';
    }

}

以上给出3种算法实现，以下是这个案例的输出结果：

False
False
True

分析：

显而易见，IsPowerOfThree 的时间复杂度为： ，IsPowerOfThree2 和IsPowerOfThree3 的时间复杂度为： 。