设计一种用于计算数组中 n 个不同二维点的算法

Question

public class IntersectionOfTwoSets {public class Point implements Comparable{    int x;    int y;    public Point(int x, int y) {        this.x = x;        this.y = y;    }    @Override    public int compareTo(Object o) {        if(this.x > ((Point)o).x) return 1;        if(this.x < ((Point)o).x) return -1;        if(this.y > ((Point)o).y) return 1;        if(this.y < ((Point)o).y) return -1;        return 0;    }}public Point[] intersectionOf(Point[] a, Point[] b) {    List<Point> result = new ArrayList<>();    Arrays.sort(a);    Arrays.sort(b);    for(int i = 0, j = 0; i < a.length && j < b.length; ) {        if(a[i].compareTo(b[j]) == 0) {            result.add(a[i]);            i++;            j++;        } else if (a[i].compareTo(b[j]) < 0) {            i ++;        } else {            j ++;        }    }    return (Point[])result.toArray();}给定两个数组 a 和 b，包含 n 个不同的 2D 点。设计一个算法来计算两个数组中包含的点数（难以理解代码）我有多个与此代码相关的问题：为什么我们要创建嵌套类？为什么我们在 else if 主体中增加 i 和 j 而不是在 for 语句中增加它们？main 方法如何创建两个 Point 数组的对象？（如果有人对这个问题有更好的解决方案，非常感谢。）

Answer 1

我使用 C++，但我可以回答你的问题。

1）我们为什么要创建嵌套类？

避免类型冲突

+- IntersectionOfTwoSets (class) ------+

|    |                                 |

|    o- Point (class)                  |

|    |                                 |

|    o- intersectionOf (function)      |

|                                      |

+--------------------------------------+

可以在没有的情况下实现，IntersectionOfTwoSets但请注意这Point是一个非常常见的名称，并且可能已经在您打算添加到项目中的任何库中实现。实现PointinIntersectionOfTwoSets使您的实现独一无二（在 C++ 中称为一个概念namespace，使用它被认为是良好的编程实践）

循环语法的标准是： for( init; condition; increment)

观察循环的增量组件丢失，而不是在循环中找到它

2）intersectionOf方法中的i++和j++是如何实现的？

i++很简单i += 1；

这是代码的简化版本

given two sets a & b

sort a & b

initialize empty array (result)

loop (...)

| if (a[i] == b[j])

|  add a[i] to result, then increment i & j

| if (a[i] < b[j])

|  increment i

| if (b[j] < a[i])

|  increment j

| if (i >= a.size()) or (j >= b.size())

|  stop

return result

让我们在一组整数上测试算法

let a: [2, 1, 10, 9]

let b: [1, 5, 2, 7, 6]

let result: []

Arrays.sort(a); // a: [1, 2, 9, 10]

Arrays.sort(b); // b: [1, 2, 5, 6, 7]

loop(...)

| 1: add 1 to result, increment i & j

| 2: add 2 to result, increment i & j

| 3: (j == 2) increment only j (5 < 9)

| 4: (j == 3) increment only j (6 < 9)

| 5: (j == 4) increment only j (7 < 9)

| 6: (j == 5) stop because j >= b.size()

return result // [1, 2]

它也应该在一组点上起作用

3) main 方法如何创建两个 Point 数组的对象？

在 C++ 中，语法是：

IntersectionOfTwoSets::Point a[n], b[n];

or

List<IntersectionOfTwoSets::Point> a, b;

但在 Java 中，我几乎可以肯定它是：

List<IntersectionOfTwoSets.Point> a, b;

or

IntersectionOfTwoSets::Point a = new IntersectionOfTwoSets::Point[n];

IntersectionOfTwoSets::Point b = new IntersectionOfTwoSets::Point[n];