社区首页 >专栏 >2025-04-01：统计近似相等数对Ⅰ。用go语言，给定一个正整数数组 nums，我们定义“近似相等”的一对数为：在下标 i

2025-04-01：统计近似相等数对Ⅰ。用go语言，给定一个正整数数组 nums，我们定义“近似相等”的一对数为：在下标 i

福大大架构师每日一题

发布于 2025-04-01 02:11:55

7100

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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-*-

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

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

        m = len(s)
        for i inrange(m):
            for j inrange(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


defatoi(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)