题解 | JZ44 数字序列中某一位的数字
提示：力扣的数据更强，试试提交到力扣里。
这个题意思挺清晰的，但是边界条件处理有点麻烦。
可以通过找规律发现：
0 ... 9 每个数字都是一个字符 共个字符
10 ... 99 每个数字都是两个字符 个字符
100 ... 999 每个数字都是三个字符 个字符
1000 ... 9999 每个数字都是四个字符 个字符
我们可以计算一个sum数组统计前缀和，再看看n是落在哪一个位置上。
然后根据n-sum[pos-1]，得到了多出来的部分。而这个多出来的部分除以这一组的字符数，就能得到这个数字在这一组中的位置。
假设得到的位置为p，那么我们需要判断是这个p的哪一个数字才是我们最终需要的答案。
我们让数字减少一个值，然后除以对这组数字字符的个数。就能够得到是哪一个数字，然后再对这个数字上的位数进行判断就行了。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型
*/
int findNthDigit(int n) {
// write code here
long long a[10];
long long sum[10];
a[0] = 9;
sum[0] = 9;
for (int i = 1; i <= 9; i++) {
a[i] = (pow(10, i+1) - pow(10, i)) * (i+1);
sum[i] = sum[i-1] + a[i];
}
int pos = lower_bound(sum, sum+10, n) - sum;
if (pos == 0) return n;
int remain = n - sum[pos-1];
int ci = (remain-1) / (pos+1);
int digitall = getPow(10, pos) + ci;
if (remain%(pos+1) == 0) {
return digitall % 10;
}
string tmp = to_string(digitall);
return tmp[remain%(pos+1) - 1] - '0';
}
long long getPow(int x, int n) {
long long ans = 1;
for (int i = 1; i <= n; i++) {
ans = ans * x;
}
return ans;
}
};
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#
import math
class Solution:
def findNthDigit(self , n: int) -> int:
# write code here
a = [9] * 10
suma = [9] * 10
for i in range(1, 9):
a[i] = (pow(10, i+1) - pow(10, i)) * (i+1)
suma[i] = suma[i-1] + a[i]
pos = self.lower_bound(suma, n)
if pos == 0:
return n
remain = n - suma[pos-1]
div = math.floor((remain - 1) / (pos+1))
digitall = pow(10, pos) + div
if remain % (pos+1) == 0:
return digitall % 10
return int(str(digitall)[remain%(pos+1) - 1])
def lower_bound(self, nums, target):
low, high = 0, len(nums)-1
pos = len(nums)
while low<high:
mid=(low+high)//2
if nums[mid]<=target:
low = mid+1
else:#>
high = mid
pos = high
if nums[low]>target:
pos = low
return pos
