标签搜索

目 录CONTENT

文章目录

字节--字典序.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 5 阅读 / 2,912 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

字节--字典序

@[toc]

一、题目描述

给定整数n和m, 将1到n的这n个整数按字典序排列之后, 求其中的第m个数

对于n=11, m=4, 按字典序排列依次为1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9,
 因此第4个数是2.
对于n=200, m=25, 按字典序排列依次为1 10 100 101 102 103 104 105 106 107 
108 109 11 110 111 112 113 114 115 116 117 118 119 12 120 
121 122 123 124 125 126 127 128 129 13 130 131 132 133 134
 135 136 137 138 139 14 140 141 142 143 144 145 146 147 
 148 149 15 150 151 152 153 154 155 156 157 158 159 16 
 160 161 162 163 164 165 166 167 168 169 17 170 171 172 
 173 174 175 176 177 178 179 18 180 181 182 183 184 185 
 186 187 188 189 19 190 191 192 193 194 195 196 197 198 
 199 2 20 200 21 22 23 24 25 26 27 28 29 3 30 31 32 33 
 34 35 36 37 38 39 4 40 41 42 43 44 45 46 47 48 49 5 50 
 51 52 53 54 55 56 57 58 59 6 60 61 62 63 64 65 66 67 
 68 69 7 70 71 72 73 74 75 76 77 78 79 8 80 81 82 83 84 
 85 86 87 88 89 9 90 91 92 93 94 95 96 97 98 99 
 因此第25个数是120…
  •  输入描述:
输入仅包含两个整数n和m。

数据范围: 

对于20%的数据, 1 <= m <= n <= 5 ; 

对于80%的数据, 1 <= m <= n <= 10^7 ; 

对于100%的数据, 1 <= m <= n <= 10^18.
  •  输出描述:
输出仅包括一行, 即所求排列中的第m个数字.

输入例子1:
11 4

输出例子1:
2

二、分析

同样这道题不能暴力求解,如果使用额外内存暴力排序会发现超出内存限制,同样解决这道题需要另辟捷径

  •  题目理解:求一组数字字典排序的第k个数字

  •  既然是字典序,那么很自然,我们可以考虑使用字典树来实现,但是这里并不需要真正的生成这个字典树,而只需要计算对应的分支节点数就行了。

  •  计算分支节点数,那么很简单,节点数就是上级结点*10,例如1分支总的结点数 = 1 + (1*10) + (1*10*10)+(1*10*10*10)+ .......

  •  这里需要注意最后的边界,n以内的节点数,那么,最后相加的时候必须要把 n+1~(1*10*10*......)这个几个数去除。(理解怎样计算分支节点数是此题的关键!

  •  理解怎样计算分支节点数:

  •  当都是个位时,字典数为1的有1,1个。

  •  当最大是两位时,字典树为1的有1,10 ,11,12,13,14,15…………19,个数为11个,1+ (1*10)

  •  当最大是三位是,依次类推,字典数1开始的有:1,10~19,100~199,个数为111个,1+ (1*10)+(1*10*10)

  •  ………………………………………… 其它分支字典类推。

  •  既然知道了如何计算字典树的分支节点数,要想知道第m个数是什么,那么就是找第m个结点

  •  首先从1开始,如果1分支的节点数>m ,那么第m个数肯定是以1开头的,进一步搜索其子节点,搜索子节点时不用再搜索1了,所以搜索1分支的第m-1个节点

  •  如果1分支的节点数<m,那么所查找的数肯定不是1开头,那么开始搜索2分支

  •  在2分支中,所要找的数应该是第(m-1分支节点数)个数

  •  重复这个过程,要么搜索子节点,要么搜索兄弟节点,直到最终m == 0,也就是当前节点所要搜索的节点。

三、代码

#include <iostream> 
using namespace std;

//包括自己的节点数,即字典树的数字pre分支的所有节点数
//pre分支的深度为1的孩子:pre*10,pre*10+1,pre*10+2,...,pre*10+10-1,
//孩子数为10
//pre分支的深度为2的孩子:pre*100,pre*100+1,pre*100+2,...,pre*100+100-1,
//孩子数为100
long getCntofPre(long pre,long n)
{
    long cnt = 1;
    long p =10;
    
    //pre*10是pre深度为1的第一个孩子的数字,
    //pre*100是pre深度为2的第一个孩子的数字
    //pre*p<=n,即检测在第某个深度下,是否存在该深度的第一孩子,
    //若该孩子不存在,在该深度下,肯定不会有其他孩子存在。若存在循环累加计算
    ////pre*p+p-1,即pre的某个深度下,最右边的孩子的数字(不考虑n情况)
    for(;pre * p <= n;p *= 10)
    {
    	//去除n+1 ~ (1*10*10.....)
        if(pre * p - 1 + p < n)
        {
        	//当pre=10时,109,1099,10999 <n                               					
        	//进入循环的前提是n>pre*p;                               
        	//n是数的总数
            cnt += p;
        }
        else
        {
        	//进入循环的前提是n>pre*p,如果(pre*p - 1 + p < n不成立,               
        	//则有, pre * p<=  n  <   pre*p - 1 + p 
            cnt += n + 1 - pre * p;//去除n+1 ~ (1*10*10.....)
        }
    }
    return cnt;
}
 
//该函数是寻找第m个数是什么,通过节点数进行分支选择
//如果该分支的节点数较m来说过少,那么第m的数肯定不在这个分支上,检测下个分支
//检测下个分支的时候,不是在这个分支寻找第m的数字,而是寻找第(m-上一个分支的节点数)的数
//如果分支的节点数较m来说过多, 选择该分支,如果m为1,那么答案就是这个分支的根节点
long solve(long n,long m)
{
	//默认在第1分支寻找
    long ans = 1;//字典前序
    while(m != 0)
    {         
    	long cnt = 0;
    	//获得该分支的节点数
        cnt  = getCntofPre(ans,n);
        if(cnt >= m)
        {
        	//对应分支节点数大于m个个数,所以在以ans的分支字典中寻找
            m--;    
            //找到了             
            if(m == 0)
            {
                break;
            }
            //在该分支的孩子分支上,从第一孩子开始寻找
            ans *= 10;//ans对应的是一个字典前序,如10,11,12,13,其字典分支
            //为101,102,1001,110,1100,1200,1201,1300,1301,1309,1310等
        }
        else
        {
            m -=cnt;//以ans开始的分支节点数小于m,在下一个分支节点中寻找,并令m =m-cnt;
            ans++; //下一个分支节点。
        }
 
    }
    return ans;
}
 
int main()
{
    uint64_t n,m;
    while(cin>>n>>m)
    {
        cout<<solve(n,m)<<endl;
    }
    return 0;
}
 
0

评论区