Coursera-Algorithm Week3

Posted on | In

本周的主题是Collinear Points, 作业巧妙地把模式识别的基础和排序结合在一起。在给出的点坐标的情况下，返回练成线的个数和起点终点。
课程Speficication


作业分为3个部分
1) Point.java 定义Point类，完成相关操作
2) BruteCollinearPoints.java 通过暴力算法得到有几条连成的线
3) 与2)对比的，有了FastCollinearPoints.java，我们需要自己设计算法，提高时间效率

Point.java

Point中使用了Java的Comparable与Comparator，需要细细琢磨才能明白作业的意图。不明白的同学可以参考Comparators一节最后的部分Polar order。同时注意计算斜率时的返回值为double类型。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.Comparator;
import edu.princeton.cs.algs4.StdDraw;


public class Point implements Comparable<Point> {
    private final int x;     // x-coordinate of this point
    private final int y;     // y-coordinate of this point
    public Point(int x, int y) {
        /* DO NOT MODIFY */
        this.x = x;
        this.y = y;
    }
    public void draw() {
        /* DO NOT MODIFY */
        StdDraw.point(x, y);
    }
    public void drawTo(Point that) {
        /* DO NOT MODIFY */
        StdDraw.line(this.x, this.y, that.x, that.y);
    }
    public double slopeTo(Point that) {
    	if(compareTo(that) == 0)	return Double.NEGATIVE_INFINITY;
    	if(this.y == that.y)	return +0.0;
    	if(this.x == that.x)	return Double.POSITIVE_INFINITY;
    	return (double)(that.y - this.y) / (that.x - this.x);
    }
    public int compareTo(Point that) {
        if(this.y < that.y)	return	-1;
        else if(this.y > that.y)	return 1;
        else {
        	if(this.x < that.x)	return -1;
        	else if(this.x > that.x)	return 1;
        	else	return 0;
        }
    }
    public Comparator<Point> slopeOrder() {
        /* YOUR CODE HERE */
    	return new pointComparator(this);
    }
    private class pointComparator implements Comparator<Point>{
    	private Point p;
    	public pointComparator(Point p) {
    		this.p = p;
    	}
    	@Override
    	public int compare(Point o1, Point o2) {
    		double l1 = p.slopeTo(o1);
    		double l2 = p.slopeTo(o2);
    		if(l1 < l2)	return -1;
    		else if(l1 > l2)	return 1;
    		else	return 0;
    	}
    }
    public String toString() {
        /* DO NOT MODIFY */
        return "(" + x + ", " + y + ")";
    }
    public static void main(String[] args) {

    }
}

BruteCollinearPoints.java

要求时间复杂度为n4，且不考虑5点及以上练成线的情况。其实也是个很明显的提示了，就是用循环实现。在checklist中的提示更为明显：One approach is to form a line segment only if the 4 points are in ascending order (say, relative to the natural order), in which case, the endpoints are the first and last points.

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import java.util.ArrayList;
import java.util.Arrays;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;

public class BruteCollinearPoints {
	private LineSegment[] lines;
	private int size;
	public BruteCollinearPoints(Point[] points) {
		// finds all line segments containing 4 points
		if (points == null) throw new java.lang.IllegalArgumentException();
	
		for(int i=0;i<points.length;i++) {
			if(points[i] == null)	throw new java.lang.IllegalArgumentException();
			for(int j = i+1;j<points.length;j++) {
				if(points[j] == null)	throw new java.lang.IllegalArgumentException();
				if(points[i].compareTo(points[j]) == 0)	throw new java.lang.IllegalArgumentException();
			}
		}
		Point[] ps = points.clone();
		ArrayList<LineSegment> res = new ArrayList<>();
		Arrays.sort(ps);
		int len = ps.length;
		for(int p = 0;p<len-3;p++) {
			for(int q = p+1;q<len-2;q++) {
				double pq = ps[p].slopeTo(ps[q]);
				for(int r = q+1;r <len-1;r++) {
					double qr = ps[q].slopeTo(ps[r]);
					if(pq != qr)	continue;
					for(int s =r +1;s < len;s++) {
						double rs = ps[r].slopeTo(ps[s]);
						if(qr == rs) {	
							Point[] temp = new Point[4];
							temp[0] = ps[p];
							temp[1] = ps[q];
							temp[2] = ps[r];
							temp[3] = ps[s];
							Arrays.sort(temp);
							if(ps[p] == temp[0])	res.add(new LineSegment(temp[0],temp[3]));
						}
					}
				}
			}
		}
		lines = new LineSegment[res.size()];
		size = res.size();
		for(int i=0;i<res.size();i++) {
			lines[i] = res.get(i);
		}
		
	}
	public int numberOfSegments() {
		// the number of line segments
		return size;
	}
	public LineSegment[] segments() {
		// the line segments
		return lines.clone();
	}
	public static void main(String[] args) {
		String filename = "d.txt";
		In in = new In(filename);
	    int N = in.readInt();
        Point[] points = new Point[N];
        StdDraw.clear();
        StdDraw.setPenColor(StdDraw.BLACK);
        StdDraw.setPenRadius(0.01);
        StdDraw.setXscale(0,32767);
        StdDraw.setYscale(0,32767);
        for (int i = 0; i < N; i++) {
            int x = in.readInt();
            int y = in.readInt();
            points[i] = new Point(x, y);
            points[i].draw();
        }
        StdDraw.show();
        BruteCollinearPoints b = new BruteCollinearPoints(points);
        System.out.println(b.numberOfSegments()); 
	}
}

FastCollinearPoints.java

这时候可以充分利用自己编写的comparator了。我的想法基本如下
1) 先将points按照自然顺序排序，利用Arrays.sort(points)
2) 对每一个点p(pivot),都以其comparator对points数组进行排序，需要注意的是我们不能直接对points数组排序，而是通过克隆来做到。
3) 遍历排完序的数组，并设置counter，计算每个点和第一个点（pivot）的斜率slope,如果相同斜率的点超过4个就将整个临时数组排序，临时数组的第一个点和最后一个点就是线头和线尾
如何防止重复的segment:在第三步中，检查临时数组的第一个是否等于pivot

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class FastCollinearPoints {
	private LineSegment[] lines;
	private int size;
	public FastCollinearPoints(Point[] points) {
		// finds all line segments containing 4 or more points
		if (points == null) throw new java.lang.IllegalArgumentException();
		int len = points.length;
		for(int i=0;i<len;i++) {
			if(points[i] == null)	throw new java.lang.IllegalArgumentException();
			for(int j = i+1;j<len;j++) {
				if(points[j] == null)	throw new java.lang.IllegalArgumentException();
				if(points[i].compareTo(points[j]) == 0)	throw new java.lang.IllegalArgumentException();
			}
		}
		Point[] clonePoints = points.clone();
		ArrayList<LineSegment> res = new ArrayList<>();
		if(len < 4)	{
			lines = new LineSegment[0];
			size = 0;
			return;
		}
		Arrays.sort(clonePoints);
		for(Point p : clonePoints) {
			Point[] temp = clonePoints.clone();
			Arrays.sort(temp,p.slopeOrder());
			double slope = p.slopeTo(temp[1]);
			ArrayList<Point> beLine = new ArrayList<>();
			beLine.add(p);
			beLine.add(temp[1]);
			for(int i=2;i<len;i++) {
				double slopeTemp = p.slopeTo(temp[i]);
				if(slopeTemp != slope) {
					int beLinesize = beLine.size();
					if(beLinesize >= 4) {
						int j;
						for(j=1;j<beLinesize;j++) {
							if(p.compareTo(beLine.get(j)) != -1)	break;
						}
						if(j == beLinesize)	res.add(new LineSegment(p,beLine.get(beLinesize-1)));
					}
					if(i == len -1)	break;
					beLine = new ArrayList<>();
					beLine.add(p);
					beLine.add(temp[i]);
					slope = slopeTemp;

				}else {
					beLine.add(temp[i]);
					if(i == len-1 && beLine.size() >= 4) {
						Collections.sort(beLine);
						if(beLine.get(0) == p) {
							res.add(new LineSegment(p,beLine.get(beLine.size()-1)));
						}
					}
				}
			}
		}	
		lines = new LineSegment[res.size()];
		size = res.size();
		for(int i=0;i<res.size();i++) {
			lines[i] = res.get(i);
		}
	}
    public int numberOfSegments() {
	   // the number of line segments
    	return size;
    }
    public LineSegment[] segments() {
	   // the line segments
    	return lines.clone();   //clone() for immutability test
    }
    public static void main(String[] args) {
	}
}