Question

2442. 反转之后不同整数的数目

English Version

题目描述

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

解法

方法一：哈希表

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

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

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)

class Solution {
  public int countDistinctIntegers(int[] nums) {
    Set<Integer> s = new HashSet<>();
    for (int x : nums) {
      s.add(x);
    }
    for (int x : nums) {
      int y = 0;
      while (x > 0) {
        y = y * 10 + x % 10;
        x /= 10;
      }
      s.add(y);
    }
    return s.size();
  }
}

class Solution {
public:
  int countDistinctIntegers(vector<int>& nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    for (int x : nums) {
      int y = 0;
      while (x) {
        y = y * 10 + x % 10;
        x /= 10;
      }
      s.insert(y);
    }
    return s.size();
  }
};

func countDistinctIntegers(nums []int) int {
  s := map[int]struct{}{}
  for _, x := range nums {
    s[x] = struct{}{}
  }
  for _, x := range nums {
    y := 0
    for x > 0 {
      y = y*10 + x%10
      x /= 10
    }
    s[y] = struct{}{}
  }
  return len(s)
}

function countDistinctIntegers(nums: number[]): number {
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    nums.push(Number([...(nums[i] + '')].reverse().join('')));
  }
  return new Set(nums).size;
}

use std::collections::HashSet;
impl Solution {
  pub fn count_distinct_integers(nums: Vec<i32>) -> i32 {
    let mut set = HashSet::new();
    for i in 0..nums.len() {
      let mut num = nums[i];
      set.insert(num);
      set.insert({
        let mut item = 0;
        while num > 0 {
          item = item * 10 + (num % 10);
          num /= 10;
        }
        item
      });
    }
    set.len() as i32
  }
}