算法作业第八周(leetcode)——440.K-th Smallest in Lexicographical Order
感觉这道题又是一道数学题。。。下面给出题目地址:
https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/
这题的大意是说给出一个正整数n和一个正整数k,找出1~n中按字典序排第k个的数。看上去似乎很简单,但实际上还是要经过一番思考的。
解决这道题最简单的想法就是一位一位的找,先判断第一位是几,如果第一位是2,k就必须大于第一位为1的所有数的个数,但小于等于第一位为1或2的所有数的个数。如果是3,k就必须大于第一位为1或2的所有数的个数,但小于等于第一位为1或2或3的所有数的个数。如果个数刚好相等,我们就找到了这个数并返回。
这里我就创建了一个函数,它的作用是判断在1~n范围中以一个数为前缀的数的个数,比如n=35时,以1为前缀的数有1,10-19,所以有11个,以3为前缀的有3,30-35,有7个,以25为前缀的有1个。
写完后遇到的一个比较严重的问题就是int的溢出,会overflow的地方我已经在代码中标明出来,并且改变了写法。
下面给出实现代码:
class Solution {
public:
int findKthNumber(int n, int k) {
int temp,i, temp2, num;
temp = 0;
while(1)
{
for(i=0;i<10;i++)
{
if(i==0&&temp==0)
continue;
temp2 = temp * 10 + i;
num = getValue(n,temp2);
if(num<k)
{
k-=num;
}
else
{
temp = temp2;
k--;
if(k==0)
return temp;
break;
}
}
}
return temp;
}
int getValue(int n, int temp)
{
if(n<temp)
return 0;
long long temp2 = temp;//overflow
int cnt = 0;
while(temp2<=n)
{
cnt += (temp2/temp)/10;//overflow cnt += temp2/(temp*10)
temp2*=10;
}
temp2/=10;
return cnt+min(n-temp2+1,temp2/temp);
}
};
运行结果: