题目描述
思路解析动画文字版
记牢这一句:原数入集合,反转值入集合,集合大小就是答案。集合帮我们自动去重,重复的数插进去它不涨。下面先把五个原数放进集合,再逐个反转。
把数组 1、13、10、12、31 摆好,下标 0 到 4。右边这块是我们的集合,现在是空的。第一阶段的任务很简单:从左到右把这五个原数一个一个放进集合。
指针走到下标 0,取出原数 1。前面标蓝的都是已经收进集合的原数。现在把 1 也送进去。
原数 1 进集合,面板里多出这一行。这五个原数各不相同,所以每放一个集合就涨一个,现在集合里有 1 个数。假如原数里有重复的,集合会自动合并、不会重复计。
指针走到下标 1,取出原数 13。前面标蓝的都是已经收进集合的原数。现在把 13 也送进去。
原数 13 进集合,面板里多出这一行。这五个原数各不相同,所以每放一个集合就涨一个,现在集合里有 2 个数。假如原数里有重复的,集合会自动合并、不会重复计。
指针走到下标 2,取出原数 10。前面标蓝的都是已经收进集合的原数。现在把 10 也送进去。
原数 10 进集合,面板里多出这一行。这五个原数各不相同,所以每放一个集合就涨一个,现在集合里有 3 个数。假如原数里有重复的,集合会自动合并、不会重复计。
指针走到下标 3,取出原数 12。前面标蓝的都是已经收进集合的原数。现在把 12 也送进去。
原数 12 进集合,面板里多出这一行。这五个原数各不相同,所以每放一个集合就涨一个,现在集合里有 4 个数。假如原数里有重复的,集合会自动合并、不会重复计。
指针走到下标 4,取出原数 31。前面标蓝的都是已经收进集合的原数。现在把 31 也送进去。
原数 31 进集合,面板里多出这一行。这五个原数各不相同,所以每放一个集合就涨一个,现在集合里有 5 个数。假如原数里有重复的,集合会自动合并、不会重复计。
第二阶段,逐个反转。轮到下标 0 的 1。反转就是一个小循环:从 0 开始,每次取出当前数的末位,把新数乘 10 再加上这个末位。1 走下来得到 1。
把反转值 1 丢进集合,面板里已经有这一行了,是个重复值,集合不涨,还是 5 个。这一步印证了集合去重的好处:不用自己判断有没有,插进去就行。
第二阶段,逐个反转。轮到下标 1 的 13。反转就是一个小循环:从 0 开始,每次取出当前数的末位,把新数乘 10 再加上这个末位。13 走下来得到 31。
把反转值 31 丢进集合,面板里已经有这一行了,是个重复值,集合不涨,还是 5 个。这一步印证了集合去重的好处:不用自己判断有没有,插进去就行。
第二阶段,逐个反转。轮到下标 2 的 10。反转就是一个小循环:从 0 开始,每次取出当前数的末位,把新数乘 10 再加上这个末位。10 走下来得到 1。注意 10 的末位是 0,反转过程里 0 在最前面,累到新数上等于没加,前导零就这样丢掉了,反转结果是 1。
把反转值 1 丢进集合,面板里已经有这一行了,是个重复值,集合不涨,还是 5 个。这一步印证了集合去重的好处:不用自己判断有没有,插进去就行。
第二阶段,逐个反转。轮到下标 3 的 12。反转就是一个小循环:从 0 开始,每次取出当前数的末位,把新数乘 10 再加上这个末位。12 走下来得到 21。
把反转值 21 丢进集合,面板里之前没有它,这是一个新值,集合多出一行,涨到 6 个。它就是这道题里唯一一个反转后带来的新数字。
第二阶段,逐个反转。轮到下标 4 的 31。反转就是一个小循环:从 0 开始,每次取出当前数的末位,把新数乘 10 再加上这个末位。31 走下来得到 13。
把反转值 13 丢进集合,面板里已经有这一行了,是个重复值,集合不涨,还是 6 个。这一步印证了集合去重的好处:不用自己判断有没有,插进去就行。
全部处理完。原数 1、13、10、12、31 进了集合,反转值里只有 21 是新的,其它 1、31、1、13 早就在集合里。数一数面板,一共 6 个不同的整数,这就是答案。整道题的核心只有一句:原数和反转值都塞进一个集合,看它最后有多大。
边界想清:全相同只算一个、反转全撞车不新增、单个数反转不同则算两个。核心始终是集合去重后有多大。
面试重点:原数与反转值同入一集合、集合大小即答案;反转有算术和字符串两种写法;时间近似 O(n)、空间 O(n)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def countDistinctIntegers(self, nums: List[int]) -> int: s = set(nums) for x in nums: y = int(str(x)[::-1]) s.add(y) return len(s)复杂度
- 时间：O(n·L)，n 是数组长度,L 是每个数的位数。原数入集是 O(n);每个数反转要按位处理,约 L 次操作,这里数值不超过 10 的 6 次方,L 至多 7,是个小常数,所以整体近似 O(n) 线性
- 空间：O(n)，按峰值算。额外开销主要是那个集合,最坏情况原数和反转值互不相同,集合里最多装到 2n 个数,量级是 O(n);反转过程只用几个整数变量,是常数
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问数位反转具体怎么实现,有几种写法?
追问复杂度是多少,瓶颈在哪?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
转换二维数组
LeetCode 2610 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题