HelloKenLee

Leetcode 440 K-th Smallest in Lexicographical Order 解题报告

Posted on By KenLee

题目信息

题目: 440. K-th Smallest in Lexicographical Order
难度: Hard
正确率: 23.0%
问题描述:

Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.

Note: 1 ≤ k ≤ n ≤ 109.
Example:

Input:
n: 13   k: 2

Output:
10

Explanation:
The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.
相关题目:386. Lexicographical Numbers

问题分析

  该问题大意是,给出一个正整数n,要求对1到n的正整数按照字典序排序(即 1>10>100>1000>…>11>110…),求出排好序中的第k位的数。

解题思路

  这个问题看上去不难,最笨的方法是根据字典序排好序。然后选第k个,时间复杂度为O(nlogn)。
  不过因为只要选第K个,因此使用堆来优化的话很容易做到O(klogn)。然而如果这么简单的话这题就不会是Hard难度而且只有23%的正确率了…(>.<)
  仔细观察一下其实字典序的数是有生成规律的,这让我回想起很久之前做的一题也就是386. Lexicographical Numbers。一个数a的字典序的后一个数可以在常数时间内递推出来,因此其实能做到O(n)的时间复杂度。然而肯定没有这么简单…我提交了一下O(n)的解法,果然,超时了。(毕竟386才是median难度…)
  这样只能找找规律希望能达到O(logn)甚至O(1)的解法了。
  下面记录一下我心酸痛苦的找规律过程:
  1. 首先我们不考虑k,先考虑n。先考虑n比较大,比如n=5000,我们可以写出前几项(蓝色为数字,灰色为序号):

  我们可以发现一个比较明显的规律,数字可以分为4层,每层分别是连续的1位数,2位数,3位数,4位数。而且每层相邻的数的间隔是有规律的,比如说数字10001001只相差了1;而100101相差了11;1011相差了111;12相差了1111。因此,如果我们要找的第k个数是小于n的时候,我们可以”跳着”来找:比如我们要找第k=1120个数,我们发现k>1111,因此这个数肯定不是在[1~2]这1112个数之间,而会在[2~3]之间。也就是说,我们相当于从2开始找第8(1120-1-1111)个数。 类似的,因为8 < 111,所以相当于从20开始找第7个数;因为 7 < 11, 所以相当于从200开始找第6个数,同理,最后相当于从2000开始找第5个数,因此为2005。
  然而,上面的方法只是适用于我们要找的第k个数在字典序上排n前面的情况。那么如果我要找的数在n之后呢?比如n=2345,我要找排2345之后的某一个数的值是否还遵循上面规律呢?写一下数字2345的字典序前后几项:

  从上面我们可以看出,在数字2345之后,因为少了4位数那一层,所以连续的x位数的序列号相差比原来少了:所有的3位数相差1;所有的2位数相差11;所有的1位数相差111。而且我们还能计算出数字2345排第几位:因为1位数前序为2,所以跳过1开始的1111个数。因为2位数前序为23,所以跳过20开头到22开头的333个数。因为234开头,所以跳过230~到233的44个数。最后跳过2340到2344的5个数。加上2,23,234,2345这4个数。所以2345排k=1×1111+3×111+4×11+5×1+4=1497
  有了上面的规律,我们可以看出来基本上分两种情况来考虑

  1. 若找的第k位字典序在n之前:按照最高位到最低位的间隔”跳过”寻找即可
  2. 若找的第k位字典序在n之后:先找的n在第几位,然后所有间隔减少一层,再重复跳过寻找即可   

    结果分析

  • 时间复杂度: O(logN), 准确来说是O(log10(N)),因为按照十进制位数来分可以想象成一棵10叉数,在上面进行查找。
  • 空间复杂度: O(1),没有用到额外空间。
  • 通过时间: 66 ms

主要数据结构和方法

  • int gap;: 记录某一层的”间隔”
  • int level; 用来求出n的x位前序的辅助变量
  • int now; 当前查找到的数字
  • int k; 以now为起点,还需要查找k位求得所求的数
  • bool passN; 记录now在n之前还是在n之后。因为在n之后的话”间隔”会改变

源代码

class Solution {
public:
    int findKthNumber(int n, int k) {
        int level=1,gap=1,res=n;
        while(res>=10){
            level*=10;
            gap=10*gap+1;
            res/=10;
        }
        long long now=1;
        --k;
        bool passN=false;
        while(k>0){
            long long limit=passN?(now-now%10)+9:(n/level);
            while(now<limit && k>=gap){
                ++now;
                k-=gap;
            }
            if(k==0){
                break;
            }else{
                if(passN && k>=gap){
                    k-=gap;
                    while(now%10==9){
                        now/=10;
                        gap=gap*10+1;
                    }
                    ++now;
                }else if(now==n){
                    now=now/10;
                    if(now%10!=9){
                        ++now;
                        k--;
                    }
                    passN=true;
                }else{
                    now*=10;
                    level/=10;
                    gap/=10;
                    --k;
                }
            }
        }
        return now;
    }

};