[Swift]LeetCode400.第N个数字|NthDigit

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9779008.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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).

Example 1:

Input:
3

Output:
3

Example 2:

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.

在无限的整数序列 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的一部分。

8ms

 1 class Solution {
 2     func findNthDigit(_ n: Int) -> Int {
 3         var len:Int = 1
 4         var base:Int = 1
 5         var num:Int = n
 6         while(n > 9*base*len)
 7         {
 8             num -= 9*base*len
 9             len += 1
10             base *= 10
11         }
12         var curNum:Int = (num-1)/len + base
13         var digit:Int = 0
14         var start:Int = (num-1)%len 
15         for i in start..<len
16         {
17             digit = curNum%10
18             curNum /= 10
19         }
20         return digit
21     }
22 }

8ms

 1 class Solution {
 2     func findNthDigit(_ n: Int) -> Int {
 3         guard n >= 10 else {
 4             return n
 5         }
 6         
 7         var index = 9
 8         var a = 90
 9         var zero = 2
10         var aa = 9
11         
12         while index + a * zero < n {
13             index += a * zero
14             zero += 1
15             a *= 10
16             aa = aa * 10 + 9
17         }
18 
19         let number = Int(String(Array(String(d))[e]))!
20         return number
21     }
22 }

8ms

 1 class Solution {
 2     func findNthDigit(_ n: Int) -> Int {
 3         if n <= 0 { return 0 }
 4         
 5         // Find the interval in which the digit will be
 6         var digitMultiplier = 1 // number of digits of numbers in current interval
 7         var fromLimit = 1 // start of the interval
 8         var toLimit = 10 // end of the interval
 9         var passedDigitCount = 0 // count of digits of all numbers in passed intervals
10         var nextLimitPassedDigitCount = 9 // number of passed digits if we move to the next interval
11         
12         while n > nextLimitPassedDigitCount {
13             passedDigitCount = nextLimitPassedDigitCount
14             fromLimit = toLimit
15             toLimit *= 10
16             digitMultiplier += 1
17             nextLimitPassedDigitCount += (toLimit - fromLimit) * digitMultiplier
18         }
19         
20         let n = n - passedDigitCount
21         
22         var index = n % digitMultiplier;
23         var number = 0
24         if index == 0 {
25             index = digitMultiplier
26             number = fromLimit + n / digitMultiplier - 1
27         } else {
28             number = fromLimit + n / digitMultiplier 
29         }
30                
31         for _ in index..<digitMultiplier {
32             number /= 10
33         }
34         
35         return number % 10;
36                
37     }
38 }

12ms

 1 class Solution {
 2     func findNthDigit(_ n: Int) -> Int {
 3         var ar: [Int] = [9, 180, 2700]
 4         var length = 1, multiplier = 9, startNumber = 1
 5         var nth = n
 6         while nth - length * multiplier > 0 {
 7             nth -= length * multiplier
 8             length += 1
 9             multiplier *= 10
10             startNumber *= 10 
11         }
12         
13         var numberAtNth = startNumber + (nth-1)/length
14         var str = String(numberAtNth)
15         let index = str.index(str.startIndex, offsetBy: (nth-1)%length)
16         return Int(String(str[index]))!
17     }
18 }

16ms

 1 class Solution {
 2     func f(_ n: Int) -> Int {
 3         var idx = 0 // 1 base
 4         var block_idx = 0 // 1 base
 5         var item_size = 0 // = block_idx
 6         var item_cnt = 0
 7         var block_size = 0
 8         repeat
 9         {
10             block_idx += 1
11             item_size = block_idx
12             if item_cnt == 0 {
13                 item_cnt = 9
14             } else {
15                 item_cnt *= 10
16             }
17             block_size = item_cnt * item_size
18             idx += block_size
19         } while idx < n
20         var in_block_idx = n - (idx - block_size) - 1 // 0 base
21         var item_idx = in_block_idx / item_size // 0 base
22         var in_item_idx = in_block_idx % item_size // 0 base
23         
24         var first_item = 1;
25         if (block_idx - 1 > 0) {
26             for i in 1...block_idx - 1 {
27                 first_item *= 10
28             }
29         }
30         var item = first_item + item_idx
31         var tgt = item
32         var do_times = item_size - in_item_idx - 1
33         if do_times > 0 {
34             for i in 1...do_times {
35                 tgt /= 10
36             }
37         }
38         tgt %= 10
39         return tgt        
40     }
41     
42     func findNthDigit(_ n: Int) -> Int {
43         return f(n)
44     }
45 }