
问题
在无限的整数序列 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 的时间复杂度为:
。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3871。