已知一个点集vector<point>p和点集的大小n,点都在一个二维平面上且横坐标各不相同,找到一条穿过点数最多的直线,返回值为vector<double>,代表所求直线的斜率和截距。</double></point>
class DenseLine { public: vector<double> getLine(vector<Point> p, int n) { map<pair<double, double>, int > lines; for(int i = 0; i < n; i++){ for(int j = i+1; j < n; j++){ ++lines[calLine(p[i],p[j])]; } } auto it = lines.begin(); auto maxLine = it; int max = 0; while(it != lines.end()){ if(it->second > max) maxLine = it; it++; } vector<double> res; res.push_back(maxLine->first.first); res.push_back(maxLine->first.second); return res; } //计算斜率 pair<double, double> calLine(Point p1,Point p2){ double k = (double)(p1.y - p2.y)/(double)(p1.x - p2.x); double s = (double)p1.y - (double)k*p1.x; return make_pair(k,s); } };
public class DenseLine { public double[] getLine(Point[] p, int n) { HashMap<Line,Integer> lineNum=new HashMap<Line,Integer>(); int max=0; double slope=Double.POSITIVE_INFINITY,intercept=0; //把所有线取出来求出斜率和截距,并用哈希图存储下线条和个数的键值对 for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ double k=(double)(p[j].y-p[i].y)/(p[j].x-p[i].x); double b=(double)(p[i].y-k*p[i].x); Line line=new Line(k,b); if(lineNum.containsKey(line)){ int num=lineNum.get(line)+1; lineNum.put(line,num); //不断调整最大值 if(num>max){ max=num; slope=k; intercept=b; } } else lineNum.put(line,1); } } return new double[]{slope,intercept}; } } //面向对象的编程思想 class Line{ double k; //斜率 double b; //截距 double epsilon=0.0001; //误差 public Line(double k,double b){ this.k=k; this.b=b; } //比较两个double是否相等 public boolean isEqualValue(double a,double b){ return (Math.abs(a-b)<epsilon); } //重写equals方法当此方法被重写时,通常有必要重写 hashCode 方法, //以维护 hashCode 方法的常规协定,该协定声明相等对象必须具有相等的哈希码。 public boolean equals(Object obj) { if (obj instanceof Line) { if(isEqualValue(k,((Line)obj).k)&&isEqualValue(b,((Line)obj).b)) return true; return false; } return super.equals(obj); } //HashMap对应的应该是HashSet,数据结构是哈希表,先比hashCode(),再比equals public int hashCode() { String str=String.valueOf(k)+String.valueOf(b); return str.hashCode(); } }
public class DenseLine { public double[] getLine(Point[] p, int n) { // write code here double[] ds = new double[2]; int max = 2; int t; for (int i=0; i<n; i++){ for (int j=i+1; j<n; j++){ double a = (p[i].y-p[j].y)/(p[i].x-p[j].x); double b = p[i].y - p[i].x*a; t = 2; for (int z=0; z<n ;z++){ if (z==i||z==j) continue; if (a == (p[i].y-p[z].y)/(p[i].x-p[z].x)){ t++; } } if (max < t){ t = max; ds[0] = a; ds[1] = b; } } } return ds; } }
static class Line { double k, b; public Line(double k, double b) { this.k = round(k); this.b = round(b); } double round(double x) { double e = 0.00001; return ((int) (x / e)) * e; } public int hashCode() { return (int) (k + b); } public boolean equals(Object obj) { Line l = (Line) obj; return l.b == b && l.k == k; } } public double[] getLine(Point[] p, int n) { HashMap<Line, Integer> map = new HashMap<>(); double mk = 0, mb = 0; for (int i = 0, max = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { double k = (p[i].y - p[j].y) / (p[i].x - p[j].x); double b = p[i].y - k * p[i].x; Line l = new Line(k, b); Integer cnt = map.get(l); if (cnt == null) { map.put(l, 1); cnt = 1; } else { map.put(l, ++cnt); } if (cnt > max) { max = cnt; mk = k; mb = b; } } } return new double[] { mk, mb }; }
import java.util.*; /* 思路:遍历所有的直线,求出他们的斜率,找出其中相同斜率数最多的直线,这条直线就是所需要的斜线 利用到了hashmap,斜率和斜率对应的数目构成了键值对 但是我感觉我这个复杂度很高 */ /* public class Point { int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } public Point() { this.x = 0; this.y = 0; } }*/ public class DenseLine { public double[] getLine(Point[] p, int n) { HashMap<Double,Integer> h =new HashMap<Double,Integer>(); int max=0; double temp=0.0; Point pTemp =null; for(int i=0;i<p.length;i++){ for(int j=i;j<p.length;j++){ if(p[j].x ==p[i].x){ continue; } double k=(p[j].y-p[i].y)/(p[j].x-p[i].x); if(h.get(k) ==null){ h.put(k,1); }else{ int count =h.get(k); h.put(k,count+1); } if(h.get(k)>max){ max=h.get(k); pTemp =p[i]; temp=k; } } } double s=pTemp.y-temp*pTemp.x; double [] d=new double[2]; d[0]=temp; d[1]=s; return d; } } 运行时间:301ms 占用内存:19868k
class DenseLine { public: vector<double> getLine(vector<Point> p, int n) { // write code here map<double ,map<double,int >> m; double k,b; for (int i = 0; i < p.size(); ++i) { for (int j = i + 1; j < p.size(); ++j) { k = (p[i].y - p[j].y) * 1.0 / (p[i].x - p[j].x); b = p[i].y - k * p[i].x; m[k][b] ++; } } int max = INT_MIN; vector<double > res; auto it = m.begin(); while (it != m.end()){ auto t = it ->second.begin(); while (t != it -> second.end()){ if(t -> second > max){ max = t -> second; k = it -> first; b = t -> first; } t ++; } it ++; } res.push_back(k); res.push_back(b); return res; } };
public static double[] getLine(Point[] p, int n) { //哎,这个在线编译器不支持c#泛型Dictionary,也不支持Hashtable Dictionary <Line,int> dict=new Dictionary<Line,int>(); Line line= new Line(); double slope=double.PositiveInfinity,intercept=0; int max=0; for(int i=0;i<n-1;i++) { for(int j=i+1;j<n;j++) { line.k=(double)(p[i].Y-p[j].Y)/(double)(p[i].X-p[j].X); line.b=(double)p[i].Y-(double)line.k*p[i].X; } if(dict.ContainsKey(line)) { dict[line] += 1; if (dict[line]>max) { max=dict[line]; slope=line.k; intercept=line.b; } /*或者如下 int count =(dict[line])+1; dict.Remove(line); dict.Add(line,count); if(count>max) { max=count; slope=line.k; intercept=line.b; } */ } else { dict.Add(line,1); } } return new double[] { slope, intercept }; }
//写完了看看别人的代码,都比我简洁,我就不贴代码了。这个题目还可以使用哈希表完成; 思路如下: /* 共线最多的点的个数 思路:可以看所有两点能够构造的直线的斜率,根据斜率来判断共线的点的个数 这样斜率和该斜率上点的个数就构成了一个键值对,可以使用hash表来存储 */ int maxPoints(vector<pair<int,int> >& points ) { if(points.size() == 0) return 0; int max =1; double ratio=0.0;//斜率 //开始遍历点,构造键值对 for(int i=0;i<points.size()-1;i++) { hash_map<double,int> map; int numofSame=0; int localMax=1; //从当前点和其之后的点构成的斜率 for(int j=i+1;j<points.size();j++) { //统计相同的点,横坐标相同、纵坐标相同,记为同一个点 if(points[j].first == points[i].first && points[j].second == points[i].second) { numofSame++; continue; } //斜率无穷大的,记为numeric_limits<double>::max()最大值 else if(points[j].first == points[i].first) { ratio = numeric_limits<double>::max(); } //纵坐标相同,斜率为0的情况 else if(points[j].second == points[i].second) { ratio =0.0; } else//正常情况 { ratio = (double)(points[j].second-points[i].second)/(double)(points[j].first-points[i].first); } int num; if(map.find(ratio) != map.end())//查找map,找到该斜率,找到说明多1个点共直线 map[ratio]++; else//没有该斜率存在,就是2个点 map[ratio]=2; } //开始查找某一斜率下最多的点的个数 hash_map<double,int>::iterator it = map.begin(); fo(;it!=map.end();it++) localMax = max(localMax,it->second);//找到最大的点数 localMax += numofSame;//加上相同的点值 max = max(max,localMax); //更新max值 } return max; }
public class DenseLine {
public double[] getLine(Point[] p, int n) {
// write code here
double[] re=new double[2];
int num1=0;
int num2=0;
double te1,te2;
for(int i=0;i<n-1;++i){
for(int j=i;j<n;++j){
num2=0;
if(p[j].x==p[i].x){
te1=0.0;
te2=p[j].y;
}else{
te1=(p[j].y-p[i].y)/(p[j].x-p[i].x);
te2=p[j].y-te1*p[j].x;
}
for(int k=0;k<n;++k){
if(Math.abs(p[k].y-te1*p[k].x-te2)<0.0000001){
++num2;
}
}
if(num2>num1){
re[0]=te1;
re[1]=te2;
num1=num2;
}
}
}
return re;
}
} 求每两个点的直线,并判断其他点是否在直线上。
public static double[] getLine(Point[] p, int n) { // 记录直线的k和b, 以及额外点的个数 double k = 0.0; double b = 0.0; int otherCount = 0; for (int i = 0; p != null && i < n; i++) { for (int j = i + 1; j < n; j++) { // 记录当前点的k和b double temK = (double) (p[j].y - p[i].y) / (p[j].x - p[i].x); double temB = p[j].y - temK * p[j].x; int temCount = 0; for (int l = j + 1; l < n; l++) { double temK1 = (double) (p[l].y - p[i].y) / (p[l].x - p[i].x); double temB1 = p[l].y - temK1 * p[l].x; if(temK1 == temK && temB1 == temB){ temCount ++; } } // 如果有更多的点就交换 if(temCount > otherCount){ k = temK; b = temB; otherCount = temCount; } } } if(otherCount == 0){ return new double[]{}; } return new double[]{k,b}; }
public double[] getLine(Point[] p, int n) { // write code here List<Point[]> list = new ArrayList<Point[]>(); p(p, new Point[p.length], new int[p.length], 0, list, 0); int max = 0; double[]result = new double[2]; Map<String,Integer>map = new HashMap<String, Integer>(); for (Point[] po : list) { // System.out.print(po[0].x + "," + po[0].y + "|"); // System.out.print(po[1].x + "," + po[1].y); // System.out.println(); double k = (po[0].y - po[1].y) / (po[0].x - po[1].x); double b = po[0].y - k * po[0].x; String d = k+","+b; if (map.get(d) == null) { // System.out.println(d); map.put(d,1); if (1> max) { max = 1; result[0] = k; result[1] = b; } } else { map.put(d, map.get(d) + 1); if (map.get(d)> max) { max = map.get(d); result[0] = k; result[1] = b; } } } // System.out.println(map); return result; } void p(Point[] a, Point[] aa, int[] book, int step, List<Point[]> list, int j) { if (2 == step) { list.add(new Point[]{aa[0], aa[1]}); } for (int i = 0; i < a.length; i++) { if (book[i] == 0 && i >= j) { book[i] = 1; aa[step] = a[i]; p(a, aa, book, step + 1, list, j); j++; book[i] = 0; } } }
public double[] getLine(Point[] p, int n) { // write code here int max = -1; double max_k = -1; double max_b = -1; double[] res = new double[2]; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ int num = 2; if(i == j) continue; double k = (p[j].y - p[i].y) / (p[j].x - p[i].x); double b = p[j].y - k * p[j].x; for(int l = 0; l < n; l++){ if(p[l].y == k * p[l].x + b){ num++; } } if(num > max){ max = num; max_k = k; max_b = b; } } } res[0] = max_k; res[1] = max_b; return res; }
class DenseLine { public: vector<double> getLine(vector<Point> p, int n) { int max_points=0; double max_points_k; double max_points_b; for(int i=0;i<n-1;++i) for(int j=i+1;j<n;++j) { int count=0; double k=(p[j].y-p[i].y)/(p[j].x-p[i].x); double b=p[j].y-k*p[j].x; for(int m=j+1;m<n;++m) { if(p[m].x*k+b==p[m].y) { count++; } } if(count>max_points) { max_points=count; max_points_k=k; max_points_b=b; } } return {max_points_k,max_points_b}; } };
class DenseLine: def getLine(self, p, n): # write code here if len(p)==2: k,b=self.getkb(p[0],p[1]) return [k,b] i=0 kbdict={} while i<=len(p)-1: j=i+1 while j<=len(p)-1: k,b=self.getkb(p[i],p[j]) kb=(k,b) if kb in kbdict: kbdict[kb]+=1 else: kbdict[kb]=1 j+=1 i+=1 maxpoint=0 for kb in kbdict: if maxpoint<kbdict[kb]: maxpoint=kbdict[kb] k,b=kb ans=[k,b] return ans def getkb(self,p1,p2): k=(p2.y-p1.y)/(p2.x-p1.x) b=p2.y-k*(p2.x) return k,b
/* struct Point { int x; int y; Point() : x(0), y(0) { } Point(int xx, int yy) { x = xx; y = yy; } };*/ class DenseLine { public: vector<double> getLine(vector<Point> p, int n) { // write code here map<pair<double,double>,int> map; vector<double> ans(2); for (int i=0;i<n;i++) { for (int j=i+1;j<n;j++) { double k=(p[i].y-p[j].y)/(p[i].x-p[j].x); double b = p[i].y-k*p[i].x; if (map.find({k,b})==map.end()) map[{k,b}]=1; else map[{k,b}]++; } } int max =0; for(auto it=map.begin();it!=map.end();it++) //遍历表 { if (it->second >max) //如果某一点对的出现的次数大于最大值 { ans[0]= it->first.first; //将点对的值(斜率,截距)赋给输出结果 ans[1]= it->first.second; max = it->second; } } return ans; } };
# -*- coding:utf-8 -*- # class Point: # def __init__(self, a=0, b=0): # self.x = a # self.y = b class DenseLine: def getLine(self, p, n): # write code here m = [0,0] res = {} count = 0 for i in range(n): for j in range(i+1,n): k = (p[i].y -p[j].y )/(p[i].x - p[j].x) res[k] = res.get(k,0) + 1 if res[k] > count: m[0] = k m[1] = p[i].y - p[i].x*k count = res[k] return m
// 遍历所有组合,暴力算法(暂时没想到非暴力的算法) class DenseLine { public: vector<double> getLine(vector<Point> p, int n) { // write code here map<pair<double,double>, int> mapCount; for (int i = 0; i < p.size(); i++) { for (int j = i + 1; j < p.size(); j++) { mapCount[calPair(p[i], p[j])]++; } } pair<double, double> pairResult; int max = -1; for (auto it = mapCount.begin(); it != mapCount.end(); it++) { if (it->second >max) { max = it->second; pairResult = it->first; } } vector<double> result; result.push_back(pairResult.first); result.push_back(pairResult.second); return result; } pair<double, double> calPair(Point A, Point B) { double slope; double intercept; slope = (B.y - A.y) / (B.x - A.x); intercept = B.y - slope * B.x; return make_pair(slope, intercept); } };