前言：

这道题需要算法整体时间复杂度达到O(N)才能将所有测试用例通过

运用到的数据结构 => 哈希表

解题思路：

首先数位和指的是，一个数字各个位数相加。

例子 => 123 数位和是 6，因为 1 + 2 + 3 = 6

题目要求的是

  1. 每位数字数位和小的排前面
  2. 数位和相等的，数本身小的排前面
  3. 输出排在第M位的数

那么经过我观察，我发现数位和小的排前面，和数小的排前面会导致一种有序性。

例如 N 是13那么我们会得到

1, 10, 2, 11, 3, 12, 4, 13, 5, 6, 7, 8, 9

因为我们要从1开始，遍历到N所以我们的小的数在前面就已经被遍历过了。

我们利用这个特性创建一个哈希表，在Python是字典或者defualtdict，在C++里是unordered_map<vector<int>>.

Key -> 数位和

value -> 数组，里面装的是数本身

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
"""
用例全过版
在数位和做了优化
在查找m做了优化
"""
# defaultdict ->    key: list
from collections import defaultdict

# input
n = eval(input())
m = eval(input())


# function 数位和
def f(num: int) -> int:
    SUM = 0
    while num:
        SUM += num % 10
        num //= 10
    return SUM


dic = defaultdict(list)
for num in range(1, n + 1):
    SUM = f(num)
    # number sum
    dic[SUM].append(num)

# search m
before, now = 0, 0
for lis in dic.values():
    now = len(lis)
    if before + now >= m:
        print(lis[m - before - 1])
        break
    before += now

这里提醒一下，在求数位和不要图方便使用sum(map)，因为使用函数是有开销的，并且这还是在一个loop里面，这消耗了我们大量的时间会导致部分用例通不过。