2025-04-01：统计近似相等数对Ⅰ。用go语言，给定一个正整数数组 nums，我们定义“近似相等”的一对数为：在下标 i 和 j（i < j）中，若能通过至多一次的操作使得 nums[i] 与 nums[j] 相等，我们称这对数是近似相等的。这个操作包括选择其中一个数，并交换它的两个数字位。请计算并返回这样的近似相等数对的数量。

注意：进行操作后，数字可能出现前导零。

2 <= nums.length <= 100。

1 <= nums[i] <= 1000000。

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

输出：2。

解释：

近似相等数对包括：

3 和 30 。交换 30 中的数位 3 和 0 ，得到 3 。

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

题目来自leetcode3265。

大体步骤如下：

1. 初始化数据结构:

   • 创建一个计数器 cnt，用于记录每个数字在遍历过程中的出现次数。
   • 初始化结果变量 ans 用于存储最终的近似相等对的数量。

2. 对数组进行排序:

   • 将输入的数组 nums 进行升序排序。这将使得相等的数字在排序过程中相邻，减少后续比较的复杂性。

3. 遍历数组:

   • 对排序后的数组 nums 进行迭代，逐一考虑每个数字 x。
   • 为当前数字 x 创建一个集合 set，用于存储在本次迭代中，原始数字和通过交换得到的数字。

4. 生成近似数:

   • 将当前数字 x 转换为字符串，以便进行位交换。
   • 使用嵌套循环遍历字符串的每一对不同位，执行交换操作：
     • 交换数字中的两个字符（位）。
     • 在交换后，将新的数字转换回整数并加入集合 set。
     • 交换回去，以恢复原始数字的状态，继续进行下一个交换操作。

5. 统计相似对:

   • 对当前的 set 中的每一个数字，如果该数字在计数器 cnt 中存在，说明之前有这样的数字出现过，则将重复的次数累加到 ans 中。

6. 更新计数器:

   • 在处理完每个数字后，将当前数字 x 的计数在 cnt 中加一。

7. 返回结果:

   • 遍历完成后，返回记录的总数 ans，即找出的近似相等数对的数量。

复杂度分析

• 时间复杂度:

  • 假设输入数组的长度为 n，对数组进行排序的时间复杂度为 O(n log n)。
  • 外层遍历数组的时间复杂度为 O(n)。
  • 对于每个数字，内层的双重循环生成近似数的复杂度为 O(m^2)，其中 m 为该数字的位数，最大为 7（因为1 <= nums[i] <= 1000000）。
  • 因此，时间复杂度可大致估算为 O(n * m^2)，在最坏情况下，m 最大为 7，整体时间复杂度可以简化为 O(n)。

• 空间复杂度:

  • 使用了一个哈希表 cnt 来存放数字的计数，最坏情况下其大小为 O(n)。
  • 另一个集合 set 用于存储通过交换生成的数字，最坏情况下也为 O(n)。
  • 所以总的额外空间复杂度为 O(n)。

总结：

• 总的时间复杂度：O(n)
• 总的额外空间复杂度：O(n)

Go完整代码如下：

package main

import (
	"fmt"
	"slices"
	"strconv"
)

func countPairs(nums []int) (ans int) {
	slices.Sort(nums)
	cnt := map[int]int{}
	for _, x := range nums {
		set := map[int]struct{}{x: {}} // 不交换
		s := []byte(strconv.Itoa(x))
		m := len(s)
		for i := range s {
			for j := i + 1; j < m; j++ {
				s[i], s[j] = s[j], s[i]
				set[atoi(s)] = struct{}{} // 交换一次
				s[i], s[j] = s[j], s[i]
			}
		}
		for x := range set {
			ans += cnt[x]
		}
		cnt[x]++
	}
	return
}

// 手动转 int 快一些
func atoi(s []byte) (res int) {
	for _, b := range s {
		res = res*10 + int(b&15)
	}
	return
}


func main() {
	nums := []int{3,12,30,17,21}
	result := countPairs(nums)
	fmt.Println(result)
}

Python完整代码如下：

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

def count_pairs(nums):
    nums.sort()
    cnt = {}
    ans = 0

    for x in nums:
        set_x = {x}  # 不交换
        s = list(str(x))

        m = len(s)
        for i in range(m):
            for j in range(i + 1, m):
                # 交换两个数字位
                s[i], s[j] = s[j], s[i]
                set_x.add(atoi(s))  # 交换一次
                # 交换回去
                s[i], s[j] = s[j], s[i]

        for x in set_x:
            ans += cnt.get(x, 0)
        
        # 更新计数
        cnt[x] = cnt.get(x, 0) + 1

    return ans


def atoi(s):
    res = 0
    for b in s:
        res = res * 10 + int(b)
    return res


if __name__ == "__main__":
    nums = [3, 12, 30, 17, 21]
    result = count_pairs(nums)
    print(result)