数据结构学习 jz44 数字序列中某一位的数字

本文主要是介绍数据结构学习 jz44 数字序列中某一位的数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

关键词：找规律 数学

题目：LCR 163. 找到第 k 位数字

虽然做出来了但是做了十万年，我是猪。主要还是找到准确的规律。

思路：

    //找规律

    //0-9 占了10个位置

    //10-99 占了90*2个位置

    //100-999 占了900*3个位置

    //1000-9999 占了9000*4个位置

总体求解顺序：

        1、 确定要求的数字的位数

        2、再确定数字

        3、再确定要求的数字的第b位

比如：

k==479

        1、 确定要求的数字的位数

                479-10-90*2=289>0 说明大于99

                479-10-90*2-900*3=-2411<0 说明小于999

                可以确定要求的数y是i=2位数，y在100-999区间内，这个区间的每个数都得占3个字符。

                并且说明y里我们要求的res排在100-999这个区间里的第289个字符。

        long long x=k;//注意这里不能用int 会爆long long rex = 1;//10 100 1000int i = 1;//存位数while (x >= 0)//确定位数:一点一点减，减到合适的位置 x=x-9*10^(i-1)*i{rex *= 10;i++;x = x - (rex*9) * i;//479-10-90*2-900*3=-2411}x = x + (rex * 9) * i;//479-10-90*2=289

        2、再确定数字是几

                在100-999这个区间内每个数都得占3个字符。

                a=x/i：a=289/2=96，y排在100-999这个区间里的第96个数字。

                为什么/i？因为这个区间一个数字由i个字符组成

                得到a和i，现在我们已经可以确定y了：a加上这个区间的最小数rex=100 即y=rex+a=100+96=196

long long a = x / i;//a=x/i：a=289/2=96，y排在100-999这个区间里的第96个数字//为什么/i？因为这个区间一个数字由i个字符组成
long long res = rex + a;//现在我们已经可以确定y了：a加上这个区间的最小数rex=100 即y=rex+a=100+96=196

        3、再确定要求的数字的第b位

                确定我们要求的数字在y里的位置：b = x % i=1。

                //因为求的是从左往右数的第b位，而不是我们习惯的从右往左数，所以要除的10的个数是i-b-2

                //比如1234，b是2，那么得除两次10，即i-b-2=4-2-1=1 j=<1 除了两次10

                最后求模，得到个位数，就是我们需要的。

        long long b = x % i;//还需要确定我们要求的数字在y里的位置：b = x % i=1//因为求的是从左往右数的第b位，而不是我们习惯的从右往左数，所以要除的10的个数是i-b-2//比如1234，b是2，那么得除两次10，即i-b-2=4-2-1=1 j=<1 除了两次10for(int j=0;j<=i-b-2;j++){res=res/10;}res=res%10;//求模

复杂度计算：

时间复杂度O(logk) 确定位数

空间复杂度O(1) 只用了常数个空间没有开辟新的空间存别的

代码：

class Solution {
public://找规律//0-9 占了10个位置//10-99 占了90*2个位置//100-999 占了900*3个位置//1000-9999 占了9000*4个位置//可以先确定要求的数字的位数，再确定数字，再确定要求的数字的第b位//比如：k==479//479-10-90*2=289>0 479-10-90*2-900*3=-2411<0 可以确定要求的数y是i=2位数//说明y里我们要求的res排在100-999这个区间里的第289个字符//a=x/i：a=289/2=96，y排在100-999这个区间里的第96个数字//为什么/i？因为这个区间一个数字由i个字符组成//现在我们已经可以确定y了：a加上这个区间的最小数rex=100 即y=rex+a=100+96=196//还需要确定我们要求的数字在y里的位置：b = x % i=1//因为求的是从左往右数的第b位，而不是我们习惯的从右往左数，所以要除的10的个数是i-b-2//比如1234，b是2，那么得除两次10，即i-b-2=4-2-1=1 j=<1 除了两次10//最后求模就可以啦int findKthNumber(int k) {if (k < 10) return k;k = k - 10;long long x=k;//注意这里不能用int 会爆long long rex = 1;//10 100 1000int i = 1;//存位数while (x >= 0)//确定位数:一点一点减，减到合适的位置 x=x-9*10^(i-1)*i{rex *= 10;i++;x = x - (rex*9) * i;//479-10-90*2-900*3=-2411}x = x + (rex * 9) * i;//479-10-90*2=289long long a = x / i;//a=x/i：a=289/2=96，y排在100-999这个区间里的第96个数字//为什么/i？因为这个区间一个数字由i个字符组成long long b = x % i;//还需要确定我们要求的数字在y里的位置：b = x % i=1long long res = rex + a;//现在我们已经可以确定y了：a加上这个区间的最小数rex=100 即y=rex+a=100+96=196//因为求的是从左往右数的第b位，而不是我们习惯的从右往左数，所以要除的10的个数是i-b-2//比如1234，b是2，那么得除两次10，即i-b-2=4-2-1=1 j=<1 除了两次10for(int j=0;j<=i-b-2;j++){res=res/10;}res=res%10;//求模return res;}
};

这篇关于数据结构学习 jz44 数字序列中某一位的数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---