如果数组中存在另一个点(p,q)，即x < p和y < q，则返回一个点(x,y)。

Question

我想做一个递归算法，在一组二维坐标上使用divide and conquer，其中(x,y)是有效的，如果集合中存在一个(p,q)，其中x < p和y < q。

我想我可以使用for循环来遍历数组中的每个坐标，并将我要找的点连同数组一起发送给一个函数，该函数会将数组分割成越来越小的数组，直到有一个大小为1的数组，然后看看数组中的点是否大于给定的点，如果条件正确，则返回print该点。

问题是，我只想打印一次点，而不是每次发现条件为真时都要打印。我越来越纠结于返回什么，所以我只想把点打印出来。

我试着用Java写了一个更简单的代码，只是为了打印一个整数是否小于另一个整数。

package ComS311HW3;

public class Test2 {
    static int arr[] = {1,2,3,4,5,6};

    static void isLessThan(int num, int arr[]) {
        if(arr.length == 1) {
            if(num < arr[0])
                System.out.println(num);
        }
        else {
         int n = arr.length;
            int arrA[] = new int[(n+1)/2];
            int arrB[] = new int[n-arrA.length];
            System.arraycopy(arr, 0, arrA, 0, arrA.length);
            System.arraycopy(arr, arrA.length, arrB, 0, arrB.length);
            isLessThan(num,arrA);
            isLessThan(num,arrB);

        }
    }

    public static void main(String[] args) {
        for(int i = 0; i < arr.length; i++) {
            isLessThan(arr[i], arr);
            }
    }
}

看了一些其他的代码，并实现了一个点类，我做了这样的工作。

package ComS311HW3;

public class Test2 { static int arr[] = {1,2,3,4,5,6};

static points isLessThan(points point, points arr[], int left, int right) {
    if(right < left)
        return null;
    if(point.getX() < arr[left].getX() && point.getY() < arr[left].getY() )
        return point;
    if(point.getX() < arr[right].getX() && point.getY() < arr[right].getY() )
        return point;
    return isLessThan(point, arr, left +1, right -1);
}

public static void main(String[] args) {
    points arr[] = new points[10];

    arr[0]= new points(1,2);
    arr[1]= new points(10,20);
    arr[2]= new points(2,4);
    arr[3]= new points(5,6);
    arr[4]= new points(7,4);
    arr[5]= new points(3,4);
    arr[6]= new points(8,9);
    arr[7]= new points(4,4);
    arr[8]= new points(2,3);
    arr[9]= new points(20,1);

    for(int i = 0; i < arr.length; i++) {
        points temp = isLessThan(arr[i], arr, 0, arr.length-1);
        if(temp != null)
            System.out.println("(" + arr[i].getX() + "," + arr[i].getY() + ") is a valid point");
    }
}

}

但只做了一个递归，还是不知道如何划分这个

Answer 1

这似乎是有效的。 但我还没有做详尽的测试。 我使用Random类生成测试点。

Random r = new Random();
Point[] pts = IntStream.range(0, 10)
        .mapToObj(
                a -> new Point(r.nextInt(20), r.nextInt(30)))
        .toArray(Point[]::new);

// show the points
for (Point pt : pts) {
    System.out.println(pt);
}

System.out.println("Searching");
Point p = findPoint(pts, new Point(10, 20));
System.out.println("Returned");
System.out.println(p == null ? "Not found" : p);

public static Point findPoint(Point[] pts, Point target) {
    if (pts.length == 1) {
        Point p = pts[0];
        if (p.x < target.x && p.y < target.y) {
            return p;
        } else {
            return null;
        }
    }

    int mid = pts.length / 2;
    Point[] a1 = new Point[mid];
    Point[] a2 = new Point[pts.length - mid];
    System.arraycopy(pts, 0, a1, 0, a1.length);
    Point p = findPoint(a1, target);
    if (p != null) {
        return p;
    }
    System.arraycopy(pts, mid, a2, 0, a2.length);
    return findPoint(a2, target);

}

打印

java.awt.Point[x=17,y=2]
java.awt.Point[x=2,y=14]
java.awt.Point[x=5,y=26]
java.awt.Point[x=8,y=14]
java.awt.Point[x=7,y=20]
java.awt.Point[x=4,y=8]
java.awt.Point[x=15,y=24]
java.awt.Point[x=9,y=14]
java.awt.Point[x=4,y=3]
java.awt.Point[x=10,y=19]
Searching
Returned
java.awt.Point[x=2,y=14]