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 82 83 84  // @Title: 直线上最多的点数 (Max Points on a Line) // @Author: 15816537946@163.com // @Date: 2019-09-03 23:33:20 // @Runtime: 8 ms // @Memory: 3.7 MB /* * @lc app=leetcode.cn id=149 lang=golang * * [149] 直线上最多的点数 * * https://leetcode-cn.com/problems/max-points-on-a-line/description/ * * algorithms * Hard (18.16%) * Likes: 71 * Dislikes: 0 * Total Accepted: 4.3K * Total Submissions: 23.8K * Testcase Example: '[[1,1],[2,2],[3,3]]' * * 给定一个二维平面，平面上有 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 * */ func maxPoints(points [][]int) int { result := 0 for i, p1 := range points { sameP, sameX := 1, 0 slopeCounts := make(map[float64]int) for j := 0; j < i; j++ { p2 := points[j] if p1[0] == p2[0] && p1[1] == p2[1] { sameP++ } else if p1[0] == p2[0] { sameX++ } else { slope := float64(p1[1]-p2[1]) / float64(p1[0]-p2[0]) if _, exists := slopeCounts[slope]; exists { slopeCounts[slope]++ } else { slopeCounts[slope] = 1 } } } result = int(math.Max(float64(result), float64(sameP+sameX))) for _, count := range slopeCounts { result = int(math.Max(float64(result), float64(count+sameP))) } } return result }