【位运算】【 数学】【 哈希映射】2857. 统计距离为 k 的点对

本文涉及知识点

位运算 数学 哈希映射

LeetCode 2857. 统计距离为 k 的点对

给你一个 二维 整数数组 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 <= 10⁶

0 <= k <= 100

k <=100

由于异或运算的结果非负，所以(x1 XOR x2) + (y1 XOR y2) 有101种情况：

即 (x1 XOR x2) = k1 (y1 XOR y2) = 100- k1。k1 ∈ \in∈ [0,100]

mPre 记录前面的数，及出现次数。对于每个数，分别枚举k1。

将x1,y1 压缩成long long ，避免写hash 函数。

时间复杂度: o(nk) n 是的coordinates长度。

代码

class Solution {
public:
    int countPairs(vector<vector<int>>& coordinates, int k) {
       unordered_map<long long, int> mPre;
    const long long llUnit = 1000'000'0;
    int iRet = 0;
        for (const auto& v : coordinates)
    {
      for (int k1 = 0; k1 <= k; k1++)
      {
        long long mask = llUnit * (v[0] ^ k1) + (v[1] ^ (k - k1));
        if (mPre.count(mask))
        {
          iRet += mPre[mask];
        }
      }
            long long tmp = llUnit * v[0] + v[1];
      mPre[tmp]++;
    }
        return iRet;
    }
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。