What is the main approach to solving Count Number of Distinct Integers After Reverse Operations?

The main approach is to reverse each number, add both the original and reversed values to a set or hash table, and return the number of distinct integers.

How do you handle duplicates in this problem?

Duplicates are automatically handled by using a set or hash table, which only stores distinct elements.

Can we optimize the space complexity for this problem?

While space complexity is generally O(n), you can optimize memory usage by removing unnecessary operations or using in-place data structures if applicable.

What is the time complexity of reversing digits for each number?

Reversing the digits for each number is done in constant time, O(1), because the number of digits is small relative to the size of the array.

Is there a more efficient way to handle the uniqueness of numbers?

Using a set or hash table is the most efficient way to track distinct numbers with O(1) time complexity for insertions and lookups.

#2442

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

反转之后不同整数的数目

给你一个由正整数组成的数组 nums 。你必须取出数组中的每个整数，反转其中每个数位，并将反转后得到的数字添加到数组的末尾。这一操作只针对 nums 中原有的整数执行。返回结果数组中不同整数的数目。示例 1：输入： nums = [1,13,10,12,31] 输出： 6 解释：…

数组哈希表数学计数

题目描述

给你一个由正整数组成的数组 nums 。

你必须取出数组中的每个整数，反转其中每个数位，并将反转后得到的数字添加到数组的末尾。这一操作只针对 nums 中原有的整数执行。

返回结果数组中不同整数的数目。

示例 1：

输入：nums = [1,13,10,12,31]
输出：6
解释：反转每个数字后，结果数组是 [1,13,10,12,31,1,31,1,21,13] 。
反转后得到的数字添加到数组的末尾并按斜体加粗表示。注意对于整数 10 ，反转之后会变成 01 ，即 1 。
数组中不同整数的数目为 6（数字 1、10、12、13、21 和 31）。

示例 2：

输入：nums = [2,2,2]
输出：1
解释：反转每个数字后，结果数组是 [2,2,2,2,2,2] 。
数组中不同整数的数目为 1（数字 2）。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

lightbulb

解题思路

方法一：哈希表

我们先用哈希表记录数组中的所有整数，然后遍历数组中的每个整数，对其进行反转，将反转后的整数添加到哈希表中，最后返回哈希表的大小即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组的长度。

1

2

3

4

5

6

7

8

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)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands how to handle uniqueness using hash-based data structures.
question_mark
Candidate demonstrates efficient handling of large input sizes (up to 10^5).
question_mark
Candidate can optimize for both time and space complexity, particularly in managing distinct elements.

warning

常见陷阱

外企场景

error
Forgetting to reverse the digits properly, especially for numbers like 10 or 100 that result in leading zeros.
error
Not using a data structure like a set or hash table to track distinct elements, leading to incorrect results.
error
Misunderstanding the problem constraints and assuming a more complex solution when a set or hash table suffices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handle negative numbers by modifying the digit reversal approach.
arrow_right_alt
Consider using a different data structure for tracking distinct elements, such as an array with sorting.
arrow_right_alt
Extend the problem to handle larger input sizes or multiple operations (e.g., repeated reversals).

help

常见问题

外企场景

继续练习

#2364 统计坏数对的数目 #2748 美丽下标对的数目 #2001 可互换矩形的组数