What is the best approach for solving Count Almost Equal Pairs I?

The optimal approach uses array scanning combined with hash table lookups to efficiently check for almost equal pairs.

How can I optimize a brute-force solution for this problem?

By using a hash table to store and lookup possible transformed versions of each number, you can reduce the time complexity significantly.

What is the time complexity of the brute-force approach in Count Almost Equal Pairs I?

The brute-force approach has a time complexity of O(n^2) as it involves checking all pairs in the array.

Can sorting the array help with solving this problem?

Yes, sorting the array can group similar numbers together, which might help identify almost equal pairs more efficiently, though this approach has a complexity of O(n log n).

What edge cases should I consider for Count Almost Equal Pairs I?

Consider cases where no two numbers are almost equal, as well as cases where all numbers are the same or differ by more than one digit.

#3265

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

统计近似相等数对 I

给你一个正整数数组 nums 。如果我们执行以下操作至多一次可以让两个整数 x 和 y 相等，那么我们称这个数对是近似相等的：选择 x 或者 y 之一，将这个数字中的两个数位交换。请你返回 nums 中，下标 i 和 j 满足 i 且 nums[i] 和 nums[j] 近似相等的数…

数组哈希表排序计数枚举

题目描述

给你一个正整数数组 nums 。

如果我们执行以下操作 至多一次 可以让两个整数 x 和 y 相等，那么我们称这个数对是 近似相等 的：

选择 x 或者 y 之一，将这个数字中的两个数位交换。

请你返回 nums 中，下标 i 和 j 满足 i < j 且 nums[i] 和 nums[j] 近似相等 的数对数目。

注意，执行操作后一个整数可以有前导 0 。

示例 1：

输入：nums = [3,12,30,17,21]

输出：2

解释：

近似相等数对包括：

3 和 30 。交换 30 中的数位 3 和 0 ，得到 3 。
12 和 21 。交换12 中的数位 1 和 2 ，得到 21 。

示例 2：

输入：nums = [1,1,1,1,1]

输出：10

解释：

数组中的任意两个元素都是近似相等的。

示例 3：

输入：nums = [123,231]

输出：0

解释：

我们无法通过交换 123 或者 231 中的两个数位得到另一个数。

提示：

2 <= nums.length <= 100
1 <= nums[i] <= 10⁶

lightbulb

解题思路

方法一：排序 + 枚举

我们可以枚举每一个数，然后对于每一个数，我们可以枚举每一对不同的数位，然后交换这两个数位，得到一个新的数，记录到一个哈希表 $\textit{vis}$ 中，表示这个数至多进行一次交换后的所有可能的数。然后计算前面枚举过的数中有多少个数在哈希表 $\textit{vis}$ 中，累加到答案中。接下来，我们将当前枚举的数加入到哈希表 $\textit{cnt}$ 中，表示当前枚举的数的个数。

这样枚举，会少统计一些数对，比如 $[100, 1]$ ，因为 $100$ 交换后的数是 $1$ ，而此前枚举过数不包含 $1$ ，因此会少统计一些数对。我们只需要在枚举之前，将数组排序，即可解决这个问题。

时间复杂度 $O(n \times (\log n + \log^3 M))$ ，空间复杂度 $O(n + \log^2 M)$ 。其中 $n$ 是数组 $\textit{nums}$ 的长度，而 $M$ 是数组 $\textit{nums}$ 中的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def countPairs(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        cnt = defaultdict(int)
        for x in nums:
            vis = {x}
            s = list(str(x))
            for j in range(len(s)):
                for i in range(j):
                    s[i], s[j] = s[j], s[i]
                    vis.add(int("".join(s)))
                    s[i], s[j] = s[j], s[i]
            ans += sum(cnt[x] for x in vis)
            cnt[x] += 1
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Check for familiarity with array scanning techniques.
question_mark
Assess ability to optimize brute-force solutions with hash tables.
question_mark
Evaluate understanding of sorting and its impact on time complexity.

warning

常见陷阱

外企场景

error
Assuming a brute-force approach is always efficient for arrays of any size.
error
Neglecting to account for edge cases where numbers cannot be made equal with a single swap.
error
Overcomplicating the solution by applying complex sorting methods where hash table lookups suffice.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow for a maximum number of allowed swaps (not just one).
arrow_right_alt
Implement a solution that can handle non-digit swaps or multiple digits being swapped.
arrow_right_alt
Optimize for larger arrays, introducing additional constraints on time or space.

help

常见问题

外企场景

继续练习

#3267 统计近似相等数对 II #3186 施咒的最大总伤害 #3371 识别数组中的最大异常值