题目

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

示例 1:输入: [[1,1],[2,2],[3,3]] 输出: 3

解释:

^

|

| o

| o

| o

+------------->

0 1 2 3 4

示例 2:输入: [[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、哈希辅助；时间复杂度O(n^2)，空间复杂度O(n^2)

func maxPoints(points [][]int) int {
   n := len(points)
   if n < 3 {
      return n
   }
   res := 2
   m := make(map[[3]int]map[int]bool)
   for i := 0; i < n; i++ {
      for j := i + 1; j < n; j++ {
         // AX+BY+C=0
         A := points[j][1] - points[i][1]
         B := points[i][0] - points[j][0]
         C := points[i][1]*points[j][0] - points[i][0]*points[j][1]
         com := gcd(gcd(A, B), C)
         A, B, C = A/com, B/com, C/com
         node := [3]int{A, B, C}
         if m[node] == nil {
            m[node] = make(map[int]bool)
         }
         m[node][i] = true
         m[node][j] = true
         if len(m[node]) > res {
            res = len(m[node])
         }
      }
   }
   return res
}

func gcd(a, b int) int {
   for a != 0 {
      a, b = b%a, a
   }
   return b
}

2、暴力法；时间复杂度O(n^3)，空间复杂度O(1)

func maxPoints(points [][]int) int {
   res := 0
   n := len(points)
   if n < 3 {
      return n
   }
   for i := 0; i < n; i++ {
      for j := i + 1; j < n; j++ {
         count := 2
         x1 := points[i][0] - points[j][0]
         y1 := points[i][1] - points[j][1]
         for k := j + 1; k < n; k++ {
            x2 := points[i][0] - points[k][0]
            y2 := points[i][1] - points[k][1]
            if x1*y2 == x2*y1 { // 斜率相同+1
               count++
            }
         }
         if count > res {
            res = count
         }
      }
   }
   return res
}

总结

Hard题目，题目类似于程序员面试金典 的 面试题16.14.最佳直线，简单一些直接暴力法，也可以借助map来优化