剑指 Offer 44. 数字序列中某一位的数字

题目描述：

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

求解

为了方便我们先不考虑0，1是第一位数。 我们先把每个数字单独考虑，如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 … 99 100 101 102 … 999 … 对于长度位1的数，它们的各个位上的数字处于[ 1 1 1, 1 ∗ 9 ∗ 1 0 0 1*9*10^0 1∗9∗100]这个范围内，对于长度为2的数字上的每一位他们处于 1 ∗ 9 ∗ 1 0 0 + 1*9*10^0 + 1∗9∗100+[ 1 1 1, 2 ∗ 9 ∗ 1 0 1 2*9*10^1 2∗9∗101]这个范围内。以次类推，我们可以得到长度为k>1的数字上的每一位的处于 1 ∗ 9 ∗ 1 0 0 + 1 ∗ 9 ∗ 1 0 1 + . . . + 1 ∗ 9 ∗ 1 0 ( k − 2 ) + 1*9*10^0 + 1*9*10^1 +...+1*9*10^{(k-2)}+ 1∗9∗100+1∗9∗101+...+1∗9∗10(k−2)+ [ 1 1 1, k ∗ 9 ∗ 1 0 ( k − 1 ) k*9*10^{(k-1)} k∗9∗10(k−1)]。 对于给定的n，先求它所处的数是几位数(len)，我们可以不断的减去 1 ∗ 9 ∗ 1 0 0 1*9*10^0 1∗9∗100， 1 ∗ 9 ∗ 1 0 1 1*9*10^1 1∗9∗101，直到 n < = 1 ∗ 9 ∗ 1 0 ( l e n − 1 ) n <= 1*9 *10 ^{(len - 1)} n<=1∗9∗10(len−1)。于是给出如下代码：

int len = 1;
while(len * 9 * Math.pow(10, len - 1) < n){
          
   
	n -= len * 9 * Math.pow(10, len - 1);
	len++;
}

使用以上代码我们可以求得n所处的位的数的长度，注意此时n已经不是从1开始的第n位数，而是从 1 0 l e n − 1 10^{len-1} 10len−1的1开始的第n位数。 我们先确定在n在第几个(x)长度为len的数上，使用如下代码即可

int x = n % len == 0 ? n/len: n/len + 1;

知道在n在第x个长度为len的数上，也就知道了n所在的数的值(val)，和n在第x个数上的哪个(t)位置上。

int val = Math.pow(10, len -1) + x - 1;
	int t = n - len*(x - 1);

求出val上的第t位即可（从高到低）。

int ret = (val%Math.pow(10, len - t + 1))/Math.pow(10, len - t);

下面是完整代码，对于n位0的情况同样适用

public int findNthDigit(int n) {
          
   
    	//求n所在的数的长度
        int len = 1;
        while(len * 9 * Math.pow(10, len - 1) < n){
          
   
	        n -= len * 9 * Math.pow(10, len - 1);
	        len++;
        }
        //求n在长度位len的数的第几个数上，如果n%len = 0，说明它就在n/len这个数上，否则在后面一个数上。
        int x = n % len == 0 ? n/len: n/len + 1;
        //求第x个数的数值
        int val = (int)Math.pow(10, len -1) + x - 1;
        //求n在第x个数的哪个位上
	    int t = n - len*(x - 1);
	    //求val的第t位上的值
        int ret = (val%(int)Math.pow(10, len - t + 1))/(int)Math.pow(10, len - t);
        return ret;
    }