LeetCode-ライン上の最大ポイント



Leetcode Max Points Line



説明:
2D平面上のn個の点が与えられた場合、同じ直線上にある点の最大数を見つけます。

例1:



Input: [[1,1],[2,2],[3,3]] Output: 3 Explanation: ^ | | o | o | o +-------------> 0 1 2 3 4

例2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Explanation: ^ | | o | o o | o | o o +-------------------> 0 1 2 3 4 5 6

注意:



  • 入力タイプは2019年4月15日に変更されました。新しいメソッドシグネチャを取得するには、デフォルトのコード定義にリセットしてください。

質問の意味:2次元平面上の点の座標のセットが与えられると、最も多くの点を見つけることができ、直線を構成します。これは、同じ線上にあることができる点の数までです。

解決策:式が直線であることがわかっていますy = k x + b y = kx + b直線上の任意の2点で取得できます。
x 1-x 2 y 1-y 2 = k frac {x1-x2} {y1-y2} = k
したがって、トラバース上の各ポイントの座標、同じ勾配はポイントの数を統計するため、最も多くを見つけるポイントの勾配を比較するために、ここでは保存されたスコアの勾配を使用し、約数分かかります

Java
class Solution { public int maxPoints(int[][] points) { if (points == null) { return 0 } if (points.length <= 2) { return points.length } int result = 0 for (int i = 0 i < points.length i++) { int max = 0 int overlap = 0 Map map = new HashMap() for (int j = i + 1 j < points.length j++) { int x = points[j][0] - points[i][0] int y = points[j][1] - points[i][1] if (x == 0 && y == 0) { overlap++ continue } int xyGcd = gcd(x, y) x /= xyGcd y /= xyGcd String k = '' + x + y map.put(k, map.getOrDefault(k, 0) + 1) max = Math.max(max, map.get(k)) } result = Math.max(result, max + 1 + overlap) } return result } public int gcd(int x, int y) { if (y == 0) { return x } return gcd(y, x % y) } }