您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

【算法题】求第N位数字,数列如下112123123412345123456

时间:02-04来源:作者:点击数:

【算法题】自增自然数列组,求第N位的数字,数列如下112123123412345123456

首先,鄙视下出这个题目的人,人为增加难度,无聊。这个题目如果之前没见过,想短时间写出来还是需要一定的脑力的,一步一步抽丝剥茧吧:

①先把该数列看成如下形式:

1

12

123

12345

123456

……

这样我们可以将每个子串单独分析,可以看出来第i个子串比第i-1个子串多一个数i,数i的长度为log10(i)+1,也就是是说第i个子串比第i-1个子串的长度长log10(i)+1。

这样就可以知道第N个数是在哪一个子串里面了。

#define maxn 10000
int num[maxn];

void init()
{
    num[0] = 0;
    num[1] = 1;
    for(int i = 2 ; i < maxn ; i ++)
    {
        num[i] = (num[i-1] + log10(i) + 1);
    }
}

②在字串里面求出该位置对应的数字

这个问题可以简化为自然数列12345678910111213……第n位是什么数字,这个就简单了:

//分析:
/**
第一步:找出给定的 n 落在几位数的范围内
自然数序列中各个数的数字分布:
1-9:       1*9
10-99:    2*90
100-999:  3*900
……
即,i * 9 * 10^i
所以,总位数sum=sum+i*9*tens;(其中,i++; tens *= 10; )
比较即可知道 n 落在几位数范围内。
例如给定n = 150,
首先一位有9个数字,所以位数可以+1,这样n-9 = 141. 然后2位的数字有2*90= 180,大于141,所以目标数字肯定是2位的。

第二步:找到具体落在哪个数字
用10+(141-1)/2 = 80

第三步:找出具体在哪一位上
用(141-1)%2=0,求出该数字(80)的第0位(即8)
*/

好吧,这个其实是Leetcode上面第400题。

最近有时间,会逐渐把leetcode题目整理出来:https://github.com/cancoo/leetcode

class Solution {
public:
    int findNthDigit(int n) {
        
        int i=1;
        long long tens=1;
        long long sum=0;
        while(sum<n)
        {
            sum+=i*9*tens;
            ++i;
            tens*=10;
        }
        --i;
        tens/=10;
        sum-=i*9*tens;
        
        //cal the gap with the lowest of this section
        long long diff=n-sum;
        long long resNum=tens+(diff-1)/i; //求出具体是哪个数字
        int resBit=(diff-1)%i;  //求出具体是这个数字的哪一位
        
        //to string and return the resNum's resBit position
        string s=to_string(resNum);
        return s[resBit]-'0';
    }
};

这里其实还是有些小坑的:首先是sum的类型,记得是long long,int太小了;然后是最后返回值,字符串记得要转换成数字(即减去'0')。

③接下来就简单了,①②组合下即可:

#include <iostream>
#include <string>
#include <stdio.h>
#include <math.h>
using namespace std;

#define maxn 10000

int num[maxn];

void init()
{
    num[0] = 0;
    num[1] = 1;
    for(int i = 2 ; i < maxn ; i ++)
    {
        num[i] = (num[i-1] + log10(i) + 1);
    }
}

int findNthDigit(int n) {

    int i=1;
    long long tens=1;
    long long sum=0;
    while(sum<n)
    {
        sum+=i*9*tens;
        ++i;
        tens*=10;
    }
    --i;
    tens/=10;
    sum-=i*9*tens;

    //gap with the lowest of this section
    long long diff=n-sum;
    long long resNum=tens+(diff-1)/i;
    int resBit=(diff-1)%i;
    //return resBit;
    //return resNum;

    //to string and return the resNum's resBit position
    string s=to_string(resNum);
    int result = s[resBit]-'0';
    cout<<result<<endl; // 这里会输出结果
    return result;
    //return s[resBit]-'0';
}

int main()
{
    init();
    int N=15, i=0, temp=-1;//这里的N就是需要求的第N位
    long long total=0;
    while(i<maxn)
    {
        i++;
        if(N-num[i]>num[i])
        {
             temp=N-num[i];
             break;
         }
        else
        {
             N-=num[i];
         }

     }
     if(temp<0)
         return -1; //error
     else
         findNthDigit(N);
}

有些小问题,极大数的边界问题,不改了。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门