字典序 Leetcode题目

太过爱你忘了你带给我的痛 2022-12-27 11:27 162阅读 0赞

1. [440. 字典序的第K小数字][440. _K]

给定整数 `n` 和 `k`，找到 `1` 到 `n` 中字典序第 `k` 小的数字。

注意：1 ≤ k ≤ n ≤ 109。

示例：

输入:
    n: 13   k: 2
    
    输出:
    10
    
    解释:
    字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

解法1:

class Solution:
        def findKthNumber(self, n: int, k: int) -> int:
            # 字典序， 按 字典排序 1 10 100 ...2
            # 1 <= k <= n <= 10^9; 
            # [1, n] 第k小的数字， 所以 字典序中数 不能超过n；
            # prefix 和 n， [1, n]中第k个数（字典排序 也就是第k小的数）
            # 十叉树
            def cal_count(n, prefix, next_prefix):
                count = 0
                while prefix <= n:
                    count += min(next_prefix, n+1) - prefix # 计算个数 所以+1
                    prefix = prefix*10  # 下移一层
                    next_prefix = next_prefix * 10
                return count
            prefix = 1  
            k = k - 1 # 第k小， 索引-1
            while k > 0:
                step = cal_count(n, prefix, prefix+1)  # 用来计算prefix移动到prefix+1需要移动多少步
                if step <= k: # 同层移动
                    k = k - step
                    prefix = prefix + 1  # 本层 右移一个
                else: # step > k; 往下层移动
                    k = k - 1 # 下移 要移动一次
                    prefix = prefix * 10
            return prefix  # prefix就是要找的值

[440. _K]: https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order/

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关字典序

一.字典序基础字典序（dictionary order），又称字母序（alphabetical order），原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两

Dear 丶/ 2024年02月19日 16:38/ 0 赞/ 80 阅读

相关 LexicographicPermute(求字典序的下一个字典序)

伪代码算法 LexicographicPermute(n) //以字典序产生排列 //输入：一个正整数n //输出：在字典序下\{1,……，n\}所有排列的列表初

骑猪看日落/ 2024年02月17日 19:33/ 0 赞/ 54 阅读

相关 LeetCode_DFS_中等_386.字典序排数

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个整数 n ，按字典序返回范围 \[1, n\] 内所有整数。你必须设计

冷不防/ 2023年10月06日 23:36/ 0 赞/ 10 阅读

相关字典序 Leetcode题目

1. [440. 字典序的第K小数字][440. _K] 给定整数 `n` 和 `k`，找到 `1` 到 `n` 中字典序第 `k` 小的数字。注意：1 ≤ k ≤ n

太过爱你忘了你带给我的痛/ 2022年12月27日 11:27/ 0 赞/ 163 阅读

相关 leetcode 440. 字典序的第K小数字【字典树】

[题解参考][Link 1] 注意会数据溢出，特判或者采用long long define debug(x) cout<<x<<": "<<(x)<<endl;

深藏阁楼爱情的钟/ 2022年11月16日 08:31/ 0 赞/ 160 阅读

相关字典序问题

统计字典序的问题：只要你知道一个字符串的字典序列呢个位置：你要知道他前面有多少个，再加一即可使用两个函数：一个是统计长度为len的总个数，一个是统计一那个字母为首的长度为l

一时失言乱红尘/ 2022年10月10日 12:30/ 0 赞/ 185 阅读

相关字典树（模板题目）

[sdut原题链接][sdut] 字典树 Time Limit: 1000MS Memory Limit: 65536KB Problem Description

我会带着你远行/ 2022年07月12日 04:41/ 0 赞/ 199 阅读

相关 leetcode 386. Lexicographical Numbers 前K个字典序数组 + 字典序排序

Given an integer n, return 1 - n in lexicographical order. For example, given 13, retur

红太狼/ 2022年06月04日 05:51/ 0 赞/ 141 阅读

相关字典序算法

算法题目：给定一个正整数，实现一个方法来求出离该整数最近的大于自身的“换位数”。什么是换位数呢？就是把一个整数各个数位的数字进行全排列，从而得到新的整数。例如53241

野性酷女/ 2022年05月27日 01:08/ 0 赞/ 204 阅读

相关【算法】字典序问题

little fairy 的第x篇博客。字典序问题描述：编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数字。

客官°小女子只卖身不卖艺/ 2022年03月14日 08:46/ 0 赞/ 240 阅读