关于二维点集交集计数Java代码的疑问及优化方案咨询

先来看你提供的代码：

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(); 
    }
}

疑问解答 #

1. 为何要创建嵌套类Point？

Java标准库中没有专门用于表示可比较二维点的类，这里把Point作为嵌套类有两个核心原因：

• 封装性：这个Point类只服务于当前的交集计算逻辑，作为内部类可以和外部的IntersectionOfTwoSets类形成紧密的逻辑关联，避免类的冗余。
• 排序需求：算法中用到了Arrays.sort()，而排序需要元素具备比较逻辑。Point类实现了Comparable接口，并重写了compareTo方法，定义了先比较x坐标、再比较y坐标的排序规则，这样数组才能被正确排序，后续的双指针匹配逻辑才能生效。

2. 为何在else if分支中递增i和j，而非在for循环的语句部分？

这是双指针算法的核心逻辑决定的：
如果把i和j放在for循环的末尾（比如for(..., i++, j++)），会强制每次循环都同时移动两个指针，但实际匹配逻辑中，我们需要根据当前点的大小关系决定移动哪一个：

• 当a[i]比b[j]小时，说明a[i]不可能在b数组的后续元素中找到匹配（因为数组已经排序），所以只需要移动i指针；
• 当b[j]比a[i]小时，同理只需要移动j指针；
• 只有当两个点相等时，才同时移动两个指针，避免重复匹配。
  如果强制同时移动指针，会直接破坏匹配逻辑，漏掉大量可能的交集点。

3. 主方法应如何创建两个Point数组？

注意你的Point类是非静态内部类，它依赖于外部类IntersectionOfTwoSets的实例才能创建对象。下面是完整的主方法示例，同时我也会建议把Point改成静态内部类（更方便）：

方案1：基于非静态内部类的创建方式

public static void main(String[] args) {
    // 先创建外部类实例
    IntersectionOfTwoSets outerInstance = new IntersectionOfTwoSets();
    
    // 创建数组a
    IntersectionOfTwoSets.Point[] a = {
        outerInstance.new Point(1, 2),
        outerInstance.new Point(3, 4),
        outerInstance.new Point(5, 6)
    };
    
    // 创建数组b
    IntersectionOfTwoSets.Point[] b = {
        outerInstance.new Point(3, 4),
        outerInstance.new Point(5, 7),
        outerInstance.new Point(1, 2)
    };
    
    // 调用交集方法并输出结果
    IntersectionOfTwoSets.Point[] intersection = outerInstance.intersectionOf(a, b);
    for (IntersectionOfTwoSets.Point p : intersection) {
        System.out.printf("(%d, %d)%n", p.x, p.y);
    }
}

方案2：将Point改为静态内部类（更推荐）

把Point类的修饰符改成public static class Point，这样就不需要依赖外部类实例，直接创建：

public static void main(String[] args) {
    IntersectionOfTwoSets.Point[] a = {
        new IntersectionOfTwoSets.Point(1, 2),
        new IntersectionOfTwoSets.Point(3, 4),
        new IntersectionOfTwoSets.Point(5, 6)
    };
    
    IntersectionOfTwoSets.Point[] b = {
        new IntersectionOfTwoSets.Point(3, 4),
        new IntersectionOfTwoSets.Point(5, 7),
        new IntersectionOfTwoSets.Point(1, 2)
    };
    
    IntersectionOfTwoSets tool = new IntersectionOfTwoSets();
    IntersectionOfTwoSets.Point[] intersection = tool.intersectionOf(a, b);
    // 输出逻辑同上
}

另外注意：你原代码中return (Point[])result.toArray();会抛出ClassCastException，因为ArrayList.toArray()返回的是Object[]，不能直接强转为Point[]，正确写法是return result.toArray(new Point[0]);。

更优解决方案：基于HashSet的O(n)时间复杂度实现 #

原算法的时间复杂度是O(n log n)（来自两次排序），如果用HashSet可以把时间复杂度降到O(n)，前提是给Point类正确重写equals()和hashCode()方法（因为HashSet依赖这两个方法判断元素是否相等）：

import java.util.*;

public class IntersectionOfTwoSets { 
    // 改成静态内部类，方便使用
    public static class Point {
        int x; 
        int y; 
        public Point(int x, int y) { 
            this.x = x; 
            this.y = y; 
        } 

        // 必须重写equals，判断两个点的坐标是否完全相同
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        // 必须重写hashCode，保证相等的点有相同的哈希值
        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    } 

    public Point[] intersectionOf(Point[] a, Point[] b) { 
        // 将数组a存入HashSet
        Set<Point> pointSet = new HashSet<>(Arrays.asList(a));
        List<Point> result = new ArrayList<>();

        // 遍历数组b，检查每个点是否在集合中
        for (Point p : b) {
            if (pointSet.contains(p)) {
                result.add(p);
                pointSet.remove(p); // 避免重复匹配（题目说点都是不同的，可省略，但更鲁棒）
            }
        }

        // 正确转换为Point数组
        return result.toArray(new Point[0]);
    }

    // 主方法示例
    public static void main(String[] args) {
        Point[] a = {new Point(1,2), new Point(3,4), new Point(5,6)};
        Point[] b = {new Point(3,4), new Point(5,7), new Point(1,2)};
        
        IntersectionOfTwoSets tool = new IntersectionOfTwoSets();
        Point[] intersection = tool.intersectionOf(a, b);
        
        for (Point p : intersection) {
            System.out.printf("(%d, %d)%n", p.x, p.y);
        }
    }
}

这个方案的优势：

• 时间复杂度更低：O(n)，适合处理大规模数据；
• 逻辑更简洁，不需要排序和双指针的复杂判断。

内容的提问来源于stack exchange，提问作者Saloni Agrawal