2025-04-03：统计近似相等数对Ⅱ。用go语言，你有一个正整数数组 nums。我们称两个整数 x 和 y 为“近似相等”，如果我们可以对其中一个数执行至多两次操作，使得它们变得相等。这些操作包括选择 x 或 y 中的一个，交换这个数字的两个数位。

你的任务是计算在 nums 中，有多少对下标为 i 和 j（满足 i < j）的数对 nums[i] 和 nums[j] 是“近似相等”的。值得注意的是，交换后得到的数字可以有前导零。

请你返回符合条件的“近似相等”数对的数量。

2 <= nums.length <= 5000。

1 <= nums[i] < 10000000。

输入：nums = [1023,2310,2130,213]。

输出：4。

解释：

近似相等数对包括：

1023 和 2310 。交换 1023 中数位 1 和 2 ，然后交换数位 0 和 3 ，得到 2310 。

1023 和 213 。交换 1023 中数位 1 和 0 ，然后交换数位 1 和 2 ，得到 0213 ，也就是 213 。

2310 和 213 。交换 2310 中数位 2 和 0 ，然后交换数位 3 和 2 ，得到 0213 ，也就是 213 。

2310 和 2130 。交换 2310 中数位 3 和 1 ，得到 2130 。

题目来自leetcode3267。

大体步骤如下：

1. 初始化与排序:

   • 首先，定义一个整数数组 pow10，它包含了10的几次幂，这样可以方便地进行位数交换后的计算。
   • 将输入数组 nums 进行排序，以便后续步骤可以依赖于已排序的数进行对比。

2. 定义必要的变量:

   • 创建一个变量 ans 用于记录近似相等数对的数量。
   • 使用一个哈希表 cnt 来计算每个数字出现的次数。
   • 创建一个数组 a 用于存储当前处理数字的每一位。

3. 遍历数组中的每个数字 x:

   • 对于每个数字 x，初始化一个集合 st 来存储在对 x 进行位交换后可能得到的所有数字，包括 x 自身。
   • 通过逐位提取数字的每一位到数组 a 中。

4. 位交换处理:

   • 双重循环遍历数组 a 中的每对数位 (i, j)（其中 i < j）进行如下操作：
     • 如果 a[i] 和 a[j] 相等则跳过该对，因为没有意义。
     • 否则，进行一次位交换，计算结果 y。
     • 将 y 加入集合 st。
     • 进行一次交换后，使用嵌套循环对更高位进行第二次交换，计算所有可能的结果并将其加入集合 st。
     • 恢复 a[i] 和 a[j] 的位置，以便处理下一个组合。

5. 统计近似相等数对:

   • 在处理完每个数字后，遍历集合 st，对于每个数字 x 中可能的结果，将其在哈希表 cnt 中的次数累加到 ans 中。这表示找到了多少个数对满足近似相等。
   • 更新哈希表 cnt，增加当前数字 x 的计数。

6. 返回结果:

   • 函数最后返回 ans 的值，即满足“近似相等”条件的数对数量。

时间复杂度分析

• 对于每个数字 x，提取它的位数大约需要 O(log10(x)) 的时间，最多处理 7 位（因为 nums[i] < 10^7）。
• 内层的两个循环遍历每个数字的不同位以进行交换，最坏情况下是 O(n^2)，其中 n 是数字的位数（最多7）。
• 因此，每个数字的整体时间复杂度是 O(n^2)，这里 n 是位数的个数，总的时间复杂度大约是 O(m * n^2)，其中 m 是数字的总量。
• 综上，总的时间复杂度可以视为 O(N * num_digits^2)，其中 N 是 nums 的长度，num_digits 是最多 7。

空间复杂度分析

• 使用了一个哈希表 cnt，它的大小与数组 nums 的长度有关，空间复杂度 O(N)。
• 对于集合 st，在最坏情况下它也可能存储所有可能生成的数，若考虑 7 位数字，最坏情况下也可以达到 O(N)。
• 整体的额外空间复杂度也是 O(N)。

因此，总结来说：

• 时间复杂度: O(N * num_digits^2)
• 空间复杂度: O(N)

Go完整代码如下：

package main

import (
	"slices"
	"fmt"
)

var pow10 = [...]int{1, 10, 100, 1000, 10000, 100000, 1000000}

func countPairs(nums []int) int {
	slices.Sort(nums)
	ans := 0
	cnt := make(map[int]int)
	a := [len(pow10)]int{}
	for _, x := range nums {
		st := map[int]struct{}{x: {}} // 不交换
		m := 0
		for v := x; v > 0; v /= 10 {
			a[m] = v % 10
			m++
		}
		for i := 0; i < m; i++ {
			for j := i + 1; j < m; j++ {
				if a[i] == a[j] { // 小优化
					continue
				}
				y := x + (a[j]-a[i])*(pow10[i]-pow10[j])
				st[y] = struct{}{} // 交换一次
				a[i], a[j] = a[j], a[i]
				for p := i + 1; p < m; p++ {
					for q := p + 1; q < m; q++ {
						st[y+(a[q]-a[p])*(pow10[p]-pow10[q])] = struct{}{} // 交换两次
					}
				}
				a[i], a[j] = a[j], a[i]
			}
		}
		for x := range st {
			ans += cnt[x]
		}
		cnt[x]++
	}
	return ans
}

func main() {
	nums := []int{1023,2310,2130,213}
	result := countPairs(nums)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from collections import defaultdict

pow10 = [1, 10, 100, 1000, 10000, 100000, 1000000]

def count_pairs(nums):
    nums.sort()
    ans = 0
    cnt = defaultdict(int)
    
    for x in nums:
        st = {x}  # 不交换
        a = []
        
        # 提取数字的每一位
        v = x
        while v > 0:
            a.append(v % 10)
            v //= 10
            
        m = len(a)
        
        for i in range(m):
            for j in range(i + 1, m):
                if a[i] == a[j]:  # 小优化
                    continue
                # 交换一次
                y = x + (a[j] - a[i]) * (pow10[i] - pow10[j])
                st.add(y)
                a[i], a[j] = a[j], a[i]
                
                # 交换两次
                for p in range(i + 1, m):
                    for q in range(p + 1, m):
                        st.add(y + (a[q] - a[p]) * (pow10[p] - pow10[q]))
                        
                a[i], a[j] = a[j], a[i]  # 恢复原状
        
        for value in st:
            ans += cnt[value]
        cnt[x] += 1  # 计数当前数字出现的次数
    
    return ans

if __name__ == "__main__":
    nums = [1023, 2310, 2130, 213]
    result = count_pairs(nums)
    print(result)