给定整数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…
[编程题]字典序
既然是字典序，那么很自然，我们可以考虑使用字典树来实现，但是，这里并不需要真的生成这个字典树，而只需要计算对应分支的节点数就行了。计算分支节点数，那么很简单，节点数就是上级节点*10，总的节点数= 1 + （1 * 10） + （1 * 10 * 10） + （1 * 10 * 10 * 10） +……，这里需要注意最后的边界，n以内的节点数，那么，最后相加的时候必须要把n+1 ~ (1 * 10 * 10 *……)这几个数去掉。
既然知道了如何计算字典树分支的节点数，要想知道第m个数是什么，那么也就是找第m个节点，首先从1开始，如果1分支的节点数>m，那么第m个数肯定是以1开头，进一步搜索其子节点，搜索子节点时不用再搜索1了，所以是搜索1分支的第m-1个节点。如果1分支的节点数<m， 那么所查找的数肯定不是1开头，那么开始搜索2分支，在2分支中，所要找的数应该是第（m-（1分支节点数））个数。重复这个过程，要么搜索子节点，要么搜索兄弟节点，知道最终m==0，也就是当前节点就是所要搜索的节点。为了便于理解，简单修改了下java代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
long n = sc.nextLong();
long m = sc.nextLong();
System.out.println(solve(n, m));
}
}
private static long solve(long n, long m) {
long ans = 1;
while (m != 0) {
long cnt = getCntOfPre(ans, n);
if(cnt >= m) {
m --;
if(m == 0)
break;
ans *= 10;
} else {
m -= cnt;
ans ++;
}
}
return ans;
}
private static long getCntOfPre(long pre, long n) {
long cnt = 1;
long p = 10;
for (; pre * p <= n; p *= 10) {
if (pre * p - 1 + p < n)
cnt += p;
else
cnt += n - pre * p + 1;
// cnt += Math.min(n, pre * p - 1 + p) - pre * p + 1;
}
return cnt;
}
}
编辑于 2017-08-17 09:46:00
回复(8)
//将字典序视作一个树，寻找m次则循环m次来找寻结果
//如果在这个区间内则M在这个区间内查找，否则让梯度乘以10向上查找，知道找寻一个区间内，让i+1一个一个查找
//第一步while循环是判断是否查到这个位置，第二次则是写出num在这个区间内有多少个数
//本题不用构造一颗字典序树，却用到树的概念
//以十个十个数为区间计算
//此上均是自己的一点看法，本人不才，望指教
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
long n, m;
cin >> n >> m;
long i = 1;
m--;
while (m != 0){
long start = i, end = i + 1;
long num = 0;
while (start <= n)
{
num += min(n+1,end)- start;
start *= 10;
end *= 10;
}
if (num > m)
{
i *= 10;
m--;
}
else
{
m -= num;
i++;
}
}
cout << i << endl;
return 0;
}
发表于 2017-11-27 16:45:02
回复(3)
虽然只有50分但是这绝壁是最快的方法 不想思考的时候可以用着试试拿一些保底分
暴力生成字典序 哈哈哈
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> ve;
int main(){
int n, m;
cin>>n>>m;
for(int i = 1; i <= n; i++)
ve.push_back(to_string((long long)i));
sort(ve.begin(), ve.end());
cout<<ve[m-1]<<endl;
return 0;
}
发表于 2018-10-05 16:56:52
回复(9)
人比较笨，看了别人的代码和解释，捣鼓了很久，注释了一下，希望对后面学习的人理解有帮助！
#include <iostream>
using namespace std;
/***************************
题目理解：求一组数字字典排序的第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,也就是当前节点所要搜
索的节点。
***********************/
long getCntofPre(long pre,long n){
long cnt = 1;
long p =10;
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;
}
long solve(long n,long m){
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;
}
发表于 2018-08-02 16:33:30
回复(1)
/*超时了。。。只过了 百分之八十，按照字典序的排序规则，自己编了个next函数，就是当前数的下一个字典序的数。。。。虽然没过。。也算个小思路吧望勿喷*/
#include <iostream>
using namespace std;
long long n = 0, m = 0;
int chang = 0;
int leng(long long x)
{
int i = 0;
while (x != 0)
{
x = x / 10;
i++;
}
return i;
}
long long next(long long x)
{
int ppp = leng(x);
int last = 0;
if (ppp < chang && x * 10 <= n)
{
return x * 10;
}
else
{
last = x % 10;
if (last + 1 < 10 && x + 1 <= n)
{
return x + 1;
}
else
{
if (last + 1 == 10)
{
x = x / 10 + 1;
last = x % 10;
while (last == 0)
{
x = x / 10;
last = x % 10;
}
return x;
}
else
{
if (x + 1 > n)
{
return x / 10 + 1;
}
}
}
}
return 0;
}
int main()
{
cin >> n >> m;
chang = leng(n);
long long ans = 1;
long long i = 0;
for (i = 1; i < m; i++)
{
// cout << ans << " ";
ans = next(ans);
}
// cout << endl;
cout << ans;
return 0;
}
using namespace std;
long long n = 0, m = 0;
int chang = 0;
int leng(long long x)
{
int i = 0;
while (x != 0)
{
x = x / 10;
i++;
}
return i;
}
long long next(long long x)
{
int ppp = leng(x);
int last = 0;
if (ppp < chang && x * 10 <= n)
{
return x * 10;
}
else
{
last = x % 10;
if (last + 1 < 10 && x + 1 <= n)
{
return x + 1;
}
else
{
if (last + 1 == 10)
{
x = x / 10 + 1;
last = x % 10;
while (last == 0)
{
x = x / 10;
last = x % 10;
}
return x;
}
else
{
if (x + 1 > n)
{
return x / 10 + 1;
}
}
}
}
return 0;
}
int main()
{
cin >> n >> m;
chang = leng(n);
long long ans = 1;
long long i = 0;
for (i = 1; i < m; i++)
{
// cout << ans << " ";
ans = next(ans);
}
// cout << endl;
cout << ans;
return 0;
}
编辑于 2018-08-03 21:10:45
回复(0)
import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()){ long n =sc.nextLong(); long m =sc.nextLong(); long i = 1;//从1开始数 m--; while(m!=0){ long num = 0; long start = i,end = i+1; while(start<=n){ num += Math.min(n+1,end)-start; start*=10; end*=10; } if(num>m){ i *= 10; m--; }else{ m-=num; i++; } } System.out.println(i); } } }
编辑于 2017-08-22 16:53:24
回复(3)
import sys
n,m = sys.stdin.readline().strip("\n").split(" ")
m = int(m)
def get_cap_num(a,b,c,d):
"""
求区间[a,b]和[c,d)的交
"""
if c>b or d<=a:
return 0
else:
return max(min(b,d)-max(a,c),0) + int(b<d)
high = len(n)
cur = 0
path = ""
node = 0
a,b = [10**(len(n)-1),int(n)]
while node<m:
#第一层节点没有零
if cur == 0:
tree = [10**(high-cur-1)*x for x in range(1,12)]
leaf = []
for i in range(0,10):
#第一层节点下各自连接的最下层节点数
leaf.append(get_cap_num(a,b,tree[i],tree[i+1]))
else:
tree = [int(path)*10**(high-cur)+x*10**(high-cur-1) for x in range(0,11)]
leaf = []
for i in range(0,10):
#第cur层节点各自连着的节点数
leaf.append(get_cap_num(a,b,tree[i],tree[i+1]))
#print(leaf)
base = int("1"*(high-cur-1)) if high-cur>1 else 0
#向下进一步要加1
index = node + 1
node_num = [index]
for i in range(10):
#计算当前节点的右节点的索引值,需要加完全10叉树的值和最下层节点数
index = index + base + leaf[i]
node_num.append(index)
# 二分查找
binary = [x for x in node_num if x<= m]
if cur == 0:
path += str(len(binary))
else:
path += str(len(binary)-1)
cur += 1
#进入node节点的下层节点查找
node = binary[-1]
print path
关键在于除了最小面一层，其他层数目都好计算。我们需要构造函数去区间[a,b]和[c,d)的交点个数,那么我们就可以计算出当前节点下有多少节点在最下层，那么就可计算出它与它的右节点的差。注意到[10**(len(n)-1),int(n)]为最下层节点。
发表于 2018-08-12 17:59:51
回复(0)
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; ll solve(ll n,ll m){ //考虑一颗完全10叉树，树的所有节点就是1-n，要求的就是前序遍历的第m个节点 //m是可以走的步数 ll i=1; m--; while(m!=0){ //计算i到i+1的字典序中间相隔的个数 ll s=i,e=i+1; ll num=0; //防止越界 while(s<=n){ //计算每一层相差的个数 //n+1: 比如20-29其实是10个，而e就不用+1，因为e在这里表示30(40/50...) num+=min(n+1,e)-s; s*=10; e*=10; } if(m<num){ //向下 i*=10; //走一步 m--; }else{ //向右 i++; //对前序遍历来说，走了num步 m-=num; } } return i; } int t; ll n, m; int main() { scanf("%d",&t); while (t--){ scanf("%lld%lld",&n,&m); printf("%lld\n",solve(n,m)); } return 0; } |
| |
编辑于 2019-03-16 22:25:56
回复(0)
AC 代码，27毫秒， python 3.5.2.
通过找规律，计算含有特定前缀的数字个数（这个是关键）；
按字典序更新这个前缀，直到找到第m个字典序的数字。
复杂度 O(log10(n))参考代码
def cnt_with_digit_prefix(upper,pre):
"""Count the amount of numbers(<=upper) whose digits start with 'pre'."""
assert isinstance(upper,(int,str))
assert isinstance(pre,(int,str))
assert int(upper) > 0
upper,pre = str(upper),str(pre)
len_u,len_p = len(upper),len(pre)
if len_u < len_p or pre.startswith('0'): return 0 # not a valid number starting with '0'.
pre_upper = upper[:len_p]
if pre < pre_upper: return int('1'*(1+len_u-len_p))
if pre > pre_upper: return int('1'*(len_u-len_p)) if len_u>len_p else 0
return int('1'*(len_u-len_p))+1+int(upper[len_p:]) if len_u>len_p else 1
n,m = list(map(int,input().split()))
assert n > 0
assert m > 0
assert m <= n
digits = tuple(str(x) for x in range(10))
prefix,rank = '',0
while rank < m:
for i in range(len(digits)):
d = digits[i]
num = cnt_with_digit_prefix(n,prefix+d)
if rank + num >= m: break
rank += num
prefix += digits[i] # append to the prefix
rank += 1 # as now the 'prefix' take one place in the dictionary.
print(prefix)
编辑于 2018-11-17 16:46:05
回复(0)
-
import java.util.Scanner;
-
public class Main { -
//包括自己的节点数，即字典树的数字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
-
private static long getAllChildCount(long pre,long n){ -
long count=1;//计算自己的节点数
-
//pre*10是pre深度为1的第一个孩子的数字,pre*100是pre深度为2的第一个孩子的数字
-
//pre*p<=n,即检测在第某个深度下，是否存在该深度的第一孩子，若该孩子不存在，在该深度下，肯定不会有其他孩子存在。若存在循环累加计算
-
//pre*p+p-1,即pre的某个深度下，最右边的孩子的数字（不考虑n情况）
-
for(long p=10;pre*p<=n;p*=10){ -
if(pre*p+p-1<=n) count+=p;
-
else count+=(n-pre*p+1);//这里+1是因为[1,n],n也要算进去
-
}
-
return count;
-
}
-
-
//该函数是寻找第m个数是什么，通过节点数进行分支选择
-
//如果该分支的节点数较m来说过少，那么第m的数肯定不在这个分支上，检测下个分支
-
//检测下个分支的时候，不是在这个分支寻找第m的数字，而是寻找第（m-上一个分支的节点数）的数
-
//如果分支的节点数较m来说过多， 选择该分支，如果m为1，那么答案就是这个分支的根节点
-
private static long find(long n,long m){ -
long ans=1;//默认在第1分支寻找
-
while(m!=0){ -
long v=getAllChildCount(ans, n);//获得该分支的节点数
-
if(v<m) { -
m-=v;
-
ans++;//检测下一个分支
-
continue;
-
}
-
//找到了
-
if(m==1) break;
-
//在该分支的孩子分支上,从第一孩子开始寻找
-
ans*=10;
-
m--;//是在孩子分支的第m-1个上
-
}
-
return ans;
-
}
-
//注意是long
-
public static void main(String[] argv){ -
Scanner input=new Scanner(System.in);
-
long n=input.nextLong();
-
long m=input.nextLong();
-
System.out.println(find(n,m));
-
}
-
}
发表于 2018-11-07 16:01:30
回复(0)
给出一个没有AC的思路：这可能是最便于理解的思路了，但是运行超时，内存爆炸
这题估计要通过字典树来实现了，等用字典树实现AC了，在来补充答案
不通过
您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为40.00%
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
TreeSet<Integer> set = new TreeSet<>();
while (sc.hasNext()) {
int n = sc.nextInt();
int index = sc.nextInt();
String[] nums = new String[n];
for (int i = 0; i < n; i++) {
nums[i] = "" + (i + 1);
}
System.out.println(handle(nums, index));
}
}
public static String handle(String[] nums, int index) {
// 冒泡排序
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
// 按照字典进行排序，优先使用字符串排序 防止溢出
String s1 = nums[i];
String s2 = nums[j];
int length = nums[i].length() == nums[j].length() ? nums[i].length() : nums[i].length() > nums[j].length() ? nums[j].length() : nums[i].length();
int k = 0;
while (k < length) {
if (s1.charAt(k) == s2.charAt(k)) {
k++;
if (k == length ) {
//到达较小数字的末端，此时观察长度，
if (nums[i].length() > nums[j].length()) {
// 可交换元素
swap(nums, i, j);
}
//跳出循环
break;
}
continue;
}
if (s1.charAt(k) > s2.charAt(k)) {
// 可交换元素
swap(nums, i, j);
}
break;
}
}
}
return nums[index - 1];
}
private static void swap(String[] nums, int i, int j) {
String tmp = nums[j];
nums[j] = nums[i];
nums[i] = tmp;
}
}
发表于 2018-08-24 20:47:44
回复(0)
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{ long n,m,i=1; cin>>n>>m; m--; while(m!=0) { long s=i, e=i+1; long num=0; while(s <= n) { num += min(n+1,e)-s; s *= 10; e *= 10; } if(num > m) { i *= 10; m--; }else{ m -= num; i++; } } cout<<i<<endl; return 0;
}
发表于 2018-02-02 01:04:07
回复(0)
求详解，自己测试的案例都过了
您的代码已保存 段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起
求详解 #include<iostream>
#include<algorithm>
#include<sstream>
#define N 10^18
using namespace std;
int main()
{
long long m,n;
while(cin>>n>>m)
{
string a[N];
for(long long i = 0;i<n;i++) {
stringstream ss;
ss<<i+1;
a[i] = ss.str();
}
//for(long i = 0;i<n;i++) cout<<a[i]<<" ";cout<<endl;
sort(a,a+n);
//for(long i = 0;i<n;i++) cout<<a[i]<<" ";cout<<endl;
cout<<a[m-1]<<endl;
}
return 0;
}
发表于 2017-08-24 09:24:30
回复(6)
JS数组原始排序就可以啦
function dictionSort(n,m) {
var arr = [];
for(let i = 1;i <= n; i++){
arr.push(i);
}
arr = arr.sort();//按默认排序,顺序是在将元素转换为字符串，然后比较它们的UTF-16代码单元值序列时构建的
return arr[m-1];
}
console.log('11 4',dictionSort(11,4));//11 4 2
console.log('200 25',dictionSort(200,25));//200 25 120
发表于 2019-08-25 17:52:59
回复(0)
java如果不用巧劲是做不出这道题的了，O(n)都会超时。只有80%
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
long n = sc.nextLong();
long m = sc.nextLong();
System.out.println(solve(n, m));
}
}
private static long solve(long n, long m) {
int cur = 1;
for (int i = 1; i < m; ++i) {
if (cur * 10 <= n) {
cur *= 10; //扩展位数
} else {
if (cur >= n) cur /= 10; //防止越界，把越界的结果压缩
cur += 1;
while (cur % 10 == 0) cur /= 10; //进位后先缩短位数。
}
}
return cur;
}
}
编辑于 2017-08-09 23:07:25
回复(0)
字典树会超过内存限制，淦！！！
class Tri {
public:
int pre;
Tri *a[10];
Tri() {
pre = 0;
for (int i = 0; i < 10; i++) {
a[i] = NULL;
}
}
};
void T_insert(int n, Tri* t) {
Tri *ptr = t;
string str = to_string(n);
for (int j = 0; j < str.length(); j++) {
if (ptr->a[str[j] - '0'] == NULL) {
ptr->a[str[j] - '0'] = new Tri();
}
ptr = ptr->a[str[j] - '0'];
ptr->pre++;
}
}
int search(int n,Tri *t) {
int result = 0;
int sum = 0;
Tri *ptr = t;
while (ptr != NULL) {
for (int i = 0; i < 10; i++) {
if (ptr->a[i] != NULL) {
if (ptr->a[i]->pre+sum >= n) {
result = result * 10 + i;
sum++;
if (sum != n) {
ptr = ptr->a[i];
break;
}
else {
return result;
}
}
else {
sum += ptr->a[i]->pre;
}
}
}
}
return 0;
}
int main() {
Tri *t=new Tri();
int m, n;
while (cin >> m >> n) {
for (int i = 1; i <= m; i++) {
T_insert(i, t);
}
int k = search(n, t);
cout << k;
}
return 0;
}
发表于 2022-03-11 16:59:26
回复(1)
function Dctory(n,m){
console.log(Array.from(new Array(n),(v,k)=>k).map(i=>i.toString()).sort().map(Number)[m])
}
知道该学啥了吧🤣
编辑于 2021-09-24 10:07:10
回复(0)
前缀树
#include <cstdio>
#include <algorithm>
using namespace std;
long long getCount(long long pre, long long n)
{
long long cnt = 0, nfloor = 1;
for (; pre <= n; )
{
cnt += min(nfloor, n-pre+1);
nfloor *= 10;
pre *= 10;
}
return cnt;
}
int main()
{
long long n, m;
scanf("%lld %lld", &n, &m);
long long pre = 1;
while (m > 1)
{
long long cnt = getCount(pre, n);
if (cnt >= m)
{
m--;
pre *= 10;
}
else
{
m -= cnt;
pre++;
}
}
printf("%lld\n", pre);
return 0;
}
发表于 2021-03-26 14:23:37
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-11-18 11:14:22 -
2022-09-21 20:22:20
-
2022-09-15 17:29:20
-
2022-08-27 18:48:59
-
2022-08-25 12:37:32
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
