149. 直线上最多的点数

给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
| o
| o o
| o
| o o
+—————————->
0 1 2 3 4 5 6

  1. //采用查找表解决，key为两点直线的斜率，value为相同直线的点的个数
  3. func maxPoints(points [][]int) int {
  4.     //以i点为枢纽，找到与i点组成的直线的斜率相同的点
  5.     resMax := 0 //返回值
  6.     for i:=0;i<len(points);i++{
  7.         //建立一个key为两点斜率，可能为浮点数，所以才要float64，value为相同斜率点的个数 
  8.         hash := make(map[float64]int)
  9.         for j:=0;j<len(points);j++{
  10.             if i != j{ //不能是同一个点组成直线
  11.                 hash[lineSlope(points[i],points[j])]++
  12.             }
  13.         }
  15.         for _,v := range hash{
  16.             if v > resMax{ //遍历hash表，同一直线最多的点数
  17.                 resMax = v
  18.             }
  19.         }
  20.     }
  21.     return resMax + 1 //因为hash表没有统计点i它自身，所以需要加一
  22. }
  24. func lineSlope(a,b []int)float64{
  25.     return float64(a[1]-b[1]) / float64(a[0]-b[0]) //相当于(ay-by) / (ax-bx)
  26. }