统计距离为 k 的点对

标签: 位运算 数组 哈希表

难度: Medium

给你一个 二维 整数数组 coordinates 和一个整数 k ，其中 coordinates[i] = [xi, yi] 是第 i 个点在二维平面里的坐标。

我们定义两个点 (x1, y1) 和 (x2, y2) 的 距离 为 (x1 XOR x2) + (y1 XOR y2) ，XOR 指的是按位异或运算。

请你返回满足 i < j 且点 i 和点 j之间距离为 k 的点对数目。

示例 1：

输入：coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
输出：2
解释：以下点对距离为 k ：
- (0, 1)：(1 XOR 4) + (2 XOR 2) = 5 。
- (2, 3)：(1 XOR 5) + (3 XOR 2) = 5 。

示例 2：

输入：coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
输出：10
解释：任何两个点之间的距离都为 0 ，所以总共有 10 组点对。

提示：

  • 2 <= coordinates.length <= 50000
  • 0 <= xi, yi <= 106
  • 0 <= k <= 100

Submission

运行时间: 1582 ms

内存: 32.0 MB

class Solution:
    def countPairs(self, coordinates: List[List[int]], k: int) -> int:
        #两数之和
        #用枚举所有满足条件的所有可能来 代替  枚举所有选法

        #对于xj,yj 与前面的坐标匹配也就(k+1)种可能,最多只有(k+1)个数与它匹配
        #即 0+k , 1+(k-1),2+(k-2)...,k+0 枚举所有情况即可

        
        n=len(coordinates)
        Map={}
        ans=0
        for xj,yj in coordinates:
            #两数之和 枚举所有可能然后用哈希表找出答案
            for a in range(k+1):
                xi,yi=( a^xj ),( yj^(k-a) )
                if (xi,yi) in Map:
                    ans+=Map[(xi,yi)]
            Map[(xj,yj)]=Map.get(  (xj,yj),0 )+1
        
        return ans

Explain

此题解采用了哈希表来记录遍历过的坐标点，以减少查找与计算时间。对于每个点(xj, yj)，通过枚举可能的(xi, yi)，计算可能满足条件的(xi XOR xj) + (yi XOR yj) = k的情况。这是通过固定一个点，然后为每个可能的a值（从0到k），计算出可能的xi和yi，然后在哈希表中查找是否有这样的(xi, yi)存在。如果存在，这意味着这对点满足距离为k。通过这种方式，每个点只需要考虑k+1种可能的配对点，大大减少了必须考虑的总配对数。

时间复杂度: O(n*k)

空间复杂度: O(n)

class Solution:
    def countPairs(self, coordinates: List[List[int]], k: int) -> int:
        # 初始化计数器和哈希表
        n = len(coordinates)
        Map = {}
        ans = 0
        # 遍历每个点(xj, yj)
        for xj, yj in coordinates:
            # 枚举所有可能的(xi, yi)使得(xi XOR xj) + (yi XOR yj) == k
            for a in range(k+1):
                xi, yi = (a ^ xj), (yj ^ (k - a))
                # 检查是否存在已遍历的(xi, yi)
                if (xi, yi) in Map:
                    ans += Map[(xi, yi)]
            # 更新当前点(xj, yj)在哈希表中的出现次数
            Map[(xj, yj)] = Map.get((xj, yj), 0) + 1
        return ans

Explore

在题解中，对于每个点(xj, yj)，算法确实可能会对某些(xi, yi)配对进行重复计数。这是因为对于不同的(xj, yj)，可能会有相同的(xi, yi)满足条件。由于算法在检查(xi, yi)时没有考虑它们是否已经作为(xj, yj)被计算过，因此算法可能会对某些配对进行重复计数。为了避免这种重复计数，可以在哈希表中记录每个点作为(xi, yi)已经被考虑过的其他点(xj, yj)，这样可以确保每个配对只被计数一次。

题解中的算法确实没有明确地检查(xi, yi)是否在给定的coordinates数组中。这意味着如果计算出的(xi, yi)不在数组中，它们不会在哈希表中找到匹配，从而不会被计算为有效的点对。因此，只有当(xi, yi)同时在数组中时，这个点对才会被计入最终的结果。这种方式确保了只有实际存在于输入数组中的点对才被计数，符合题目的要求。

算法中使用的哈希表确实考虑了坐标点可能重复出现的情况。通过记录每个坐标点(xj, yj)在哈希表中的出现次数，算法能够在计算有效点对时考虑到这种重复情况。例如，如果一个点(xi, yi)在输入数组中出现多次，则每次这个点与另一个有效点(xj, yj)配对时，都会根据(xi, yi)的出现次数增加相应的计数。这样可以确保重复的点被正确地计入总数。

在题解的算法中，如果k的值非常小，算法的性能会比较好，因为每个点(xj, yj)需要考虑的(xi, yi)数量减少。然而，如果k的值非常大，算法的性能可能会受到影响，因为每个点需要考虑的(xi, yi)可能会非常多，导致计算量增加。为了优化这种情况，可以考虑使用更高效的数据结构如空间划分树或KD树来快速查找和计算距离，或者优化哈希表的使用策略，减少不必要的计算和查找。