设计一种用于计算数组中 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 点。设计一个算法来计算两个数组中包含的点数（难以理解代码）我有多个与此代码相关的问题：

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

2. 为什么我们在 else if 主体中增加 i 和 j 而不是在 for 语句中增加它们？

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

（如果有人对这个问题有更好的解决方案，非常感谢。）

Answer 1

我使用 C++，但我可以回答你的问题。1）我们为什么要创建嵌套类？避免类型冲突+- IntersectionOfTwoSets (class) ------+|&nbsp; &nbsp; |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;||&nbsp; &nbsp; o- Point (class)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ||&nbsp; &nbsp; |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;||&nbsp; &nbsp; o- intersectionOf (function)&nbsp; &nbsp; &nbsp; ||&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; |+--------------------------------------+可以在没有的情况下实现，IntersectionOfTwoSets但请注意这Point是一个非常常见的名称，并且可能已经在您打算添加到项目中的任何库中实现。实现PointinIntersectionOfTwoSets使您的实现独一无二（在 C++ 中称为一个概念namespace，使用它被认为是良好的编程实践）循环语法的标准是： for( init; condition; increment)观察循环的增量组件丢失，而不是在循环中找到它2）intersectionOf方法中的i++和j++是如何实现的？i++很简单i += 1；这是代码的简化版本given two sets a & bsort a & binitialize empty array (result)loop (...)| if (a[i] == b[j])|&nbsp; add a[i] to result, then increment i & j| if (a[i] < b[j])|&nbsp; increment i| if (b[j] < a[i])|&nbsp; increment j| if (i >= a.size()) or (j >= b.size())|&nbsp; stopreturn 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];orList<IntersectionOfTwoSets::Point> a, b;但在 Java 中，我几乎可以肯定它是：List<IntersectionOfTwoSets.Point> a, b;orIntersectionOfTwoSets::Point a = new IntersectionOfTwoSets::Point[n];IntersectionOfTwoSets::Point b = new IntersectionOfTwoSets::Point[n];