没有理解这道题，麻烦bobo老师赐教~

Question

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

public class Solution {     public int numberOfBoomerangs(int[][] points) {     int res = 0;     for( int i = 0 ; i < points.length ; i ++ ){     // record中存储 点i 到所有其他点的距离出现的频次     HashMap<Integer, Integer> record = new HashMap<Integer, Integer>();     for(int j = 0 ; j < points.length ; j ++)     if(j != i){     // 计算距离时不进行开根运算, 以保证精度     int dis = dis(points[i], points[j]);     if(record.containsKey(dis))     record.put(dis, record.get(dis) + 1);     else     record.put(dis, 1);     }     for(Integer dis: record.keySet())     res += record.get(dis) * (record.get(dis) - 1);     }     return res;     }     private int dis(int[] pa, int pb[]){     return (pa[0] - pb[0]) * (pa[0] - pb[0]) +     (pa[1] - pb[1]) * (pa[1] - pb[1]);     }     public static void main(String[] args) {     int[][] points = {{0, 0}, {1, 0}, {2, 0}};     System.out.println((new Solution()).numberOfBoomerangs(points));     }     }

bobo老师，看了这节课还有您的java解法，我仍然没有理解这道题，麻烦bobo老师可以点拨一下~

首先我对于题目解法的理解：遍历二维数组中的每一点，作为枢纽点i，同时在对每一个枢纽点遍历时，创建哈希表，再对二维数组每一个点j进行一次遍历，当i 不等于j时，计算他们的距离，并记录进哈希表中，代码表述如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

public int numberOfBoomerangs(int[][] points) {         //遍历二维数组的枢纽点i         for(int i = 0; i < points.length; i++){             for(int j = 0; j < points[i].length; j++){                 Map<Integer, Integer> freq = new HashMap<>();                 //遍历二维数组的每个与枢纽点i进行比较的点j                 for(int k = 0 ; k < points.length; k++){                     for(int l = 0; l < points.length; l++){                         if(points[i][j] != points[k][l]){                             //计算两点之间距离                         }                     }                 }             }         }     }

但是这样的话，每次遍历一次二维数组寻找枢纽点i，都要O(n^2)的时间复杂度，如果此时再遍历一次二维数组，寻找每个和枢纽点i比较的点j，时间复杂度就应该来到了O(n^4)，所以我也不理解您java代码开头

1	for( int i = 0 ; i < points.length ; i ++ )

为什么这样就可以取到每个枢纽点i，这样取到的不是应该是二维数组中的每一行嘛？

另外我也不理解最后的求距离的公式

1 2 3 4

private int dis(int[] pa, int pb[]){     return (pa[0] - pb[0]) * (pa[0] - pb[0]) +     (pa[1] - pb[1]) * (pa[1] - pb[1]);     }

为什么(pa[0],pa[1]),(pb[0],pb[1])可以表示两个点？这个函数传入的pa，pb应该是二维数组中的两个行啊？就像下面这样：

思考很久还是想不通，写了很多读起来很麻烦，辛苦bobo老师了！

Answer 1

liuyubobobo 2020-02-21 13:34:59

我不确定我是不是理解了你的问题。

貌似你的问题都在 points 这个二维数组上。关键在于，points 这个二维数组的定义就是：每一行代表一个点，即第一个维度的长度是 n，表示有 n 个点。

由于每个点都有两个数值，所以需要第二个维度，也就是第二个维度的大小为 2。

points[i] 表示第 i 个点。注意，此时 points[i] 是一个长度为 2 的一维数组，其中 points[i][0] 表示第 i 个点的 x 值；points[i][1] 表示第 i 个点的 y 值。

所以：

1

是的，for( int i = 0 ; i < points.length ; i ++ ) 取的是二维数组的每一行，每一行就是一个点，这一行有两个元素，第 0 个元素是 x 的值，第 1 个元素是 y 的值。

2

同理，int[] pa 表示一个点，这个点具体的坐标就是：(pa[0],pa[1])

int[] pb 是另外一个点，这个点具体的坐标就是：(pb[0],pb[1])。

看看能否理解？

继续加油！：）

• 提问者 Declee #1

  谢谢bobo老师，是我对题目中给的二维数组的理解产生了误差！