LeetCode 440. K-th Smallest in Lexicographical Order (Java版; Hard)

小咪咪 2023-07-04 08:34 28阅读 0赞

### [welcome to my blog][] ###

## LeetCode 440. K-th Smallest in Lexicographical Order (Java版; Hard) ##

#### 题目描述 ####

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.

#### 第一次做; 直接看的leetcode题解; 核心:字典序排列也就是对十叉树进行先序遍历 ####

class Solution { 
        public int findKthNumber(int n, int k) { 
            //根据题意, 第一个数是1
            int cur = 1;
            //第一个是1, 所以再找出k-1个数后就知道第k个数是多少了
            k = k-1;
            while(k>0){ 
                int steps = calSteps(n, cur, cur+1);
                //横向扩展, 相当于+steps,
                if(steps<=k){ 
                    cur +=1 ;
                    k -= steps;
                }
                //steps > k; 纵向扩展, 相当于+1
                else{ 
                    cur *= 10;
                    k-=1;
                }
                
            }
            return cur;
        }
        
        //n1 和 n2得是long类型的, int会产生溢出, 不能通过这个案例: 输入n=681692778, k=351251360, 预期结果=416126219
        private int calSteps(int n, long n1, long n2){ 
            int steps = 0;
            while(n1<=n){ 
                steps += Math.min(n2, n+1) - n1;
                n1 *= 10;
                n2 *= 10;
            }
            return steps;
        }
    }

#### 第一次做; 超时, 29/69 ####

/* 小根堆 */
    class Solution { 
        public int findKthNumber(int n, int k) { 
            //
            PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new Comparator<Integer>(){ 
                public int compare(Integer o1, Integer o2){ 
                    String str1 = String.valueOf(o1);
                    String str2 = String.valueOf(o2);
                    return str1.compareTo(str2);
                }
            });
            for(int i=1; i<=n; i++){ 
                minHeap.add(i);
            }
            for(int i=0; i<k-1; i++){ 
                minHeap.poll();
            }
            return minHeap.peek();
        }
    }

#### [leetcode最优解][leetcode] ####

![format_png][]

public int findKthNumber(int n, int k) { 
        int curr = 1;
        k = k - 1;
        while (k > 0) { 
            int steps = calSteps(n, curr, curr + 1);
            if (steps <= k) { 
                curr += 1;
                k -= steps;
            } else { 
                curr *= 10;
                k -= 1;
            }
        }
        return curr;
    }
    //use long in case of overflow
    public int calSteps(int n, long n1, long n2) { 
        int steps = 0;
        while (n1 <= n) { 
            steps += Math.min(n + 1, n2) - n1;
            n1 *= 10;
            n2 *= 10;
        }
        return steps;
    }

[welcome to my blog]: https://littlehaes.com
[leetcode]: https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/discuss/92242/ConciseEasy-to-understand-Java-5ms-solution-with-Explaination
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS9mNzhjMjY5Njc3Njg4MTkxMDMwYTdhNTA1MTEzMjI0Mi94bWxub3RlLzIyMUE0OUI3OTdCNDQ2NUQ5MTc2NDFCNUMyOUY2QjQxLzU4Nzg5?x-oss-process=image/format,png