Medium

题目描述

给你一个由正整数组成的数组 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^5
  • 1 <= nums[i] <= 10^6

解题思路

这道题的核心思路是使用哈希集合来统计不同的数字。

解题步骤：

  1. 理解题意：需要将原数组中每个数字及其反转后的数字都加入到结果中，然后统计不同数字的个数。

  2. 数字反转方法：对于一个整数，可以通过不断取模和整除来实现数字反转。例如 123 → 321，具体过程是：取个位数3，十位数2，百位数1，然后重新组合。

  3. 去重统计：使用哈希集合（Set）来自动去重，最后返回集合的大小即可。

算法流程：

  • 创建一个哈希集合
  • 遍历原数组，将每个数字添加到集合中
  • 对每个数字进行反转，将反转后的结果也添加到集合中
  • 返回集合的大小

注意事项：

  • 反转数字时要处理前导零的情况，如 10 反转后是 01，应该是 1
  • 使用集合可以自动处理重复数字的问题

这个解法时间复杂度为 O(n×log(max(nums)))，空间复杂度为 O(n)，是最直接高效的方法。

代码实现

class Solution {
public:
    int countDistinctIntegers(vector<int>& nums) {
        unordered_set<int> distinct;
        
        for (int num : nums) {
            // 添加原数字
            distinct.insert(num);
            
            // 反转数字
            int reversed = 0;
            int temp = num;
            while (temp > 0) {
                reversed = reversed * 10 + temp % 10;
                temp /= 10;
            }
            
            // 添加反转后的数字
            distinct.insert(reversed);
        }
        
        return distinct.size();
    }
};

class Solution:
    def countDistinctIntegers(self, nums: List[int]) -> int:
        distinct = set()
        
        for num in nums:
            # 添加原数字
            distinct.add(num)
            
            # 反转数字
            reversed_num = 0
            temp = num
            while temp > 0:
                reversed_num = reversed_num * 10 + temp % 10
                temp //= 10
            
            # 添加反转后的数字
            distinct.add(reversed_num)
        
        return len(distinct)

public class Solution {
    public int CountDistinctIntegers(int[] nums) {
        HashSet<int> distinct = new HashSet<int>();
        
        foreach (int num in nums) {
            // 添加原数字
            distinct.Add(num);
            
            // 反转数字
            int reversed = 0;
            int temp = num;
            while (temp > 0) {
                reversed = reversed * 10 + temp % 10;
                temp /= 10;
            }
            
            // 添加反转后的数字
            distinct.Add(reversed);
        }
        
        return distinct.Count;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var countDistinctIntegers = function(nums) {
    const distinct = new Set();
    
    for (let num of nums) {
        // 添加原数字
        distinct.add(num);
        
        // 反转数字
        let reversed = 0;
        let temp = num;
        while (temp > 0) {
            reversed = reversed * 10 + temp % 10;
            temp = Math.floor(temp / 10);
        }
        
        // 添加反转后的数字
        distinct.add(reversed);
    }
    
    return distinct.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × log(max(nums)))，其中 n 是数组长度，log(max(nums)) 是反转数字的时间复杂度
空间复杂度O(n)，哈希集合最多存储 2n 个不同的数字

相关题目