Leetcode-447 – Number of boomerangs

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

Given n pairs of different points on the plane, where points[I] = [xi, yi]. Boomerangs are tuples represented by points (I, j, k) where the distance between I and j is the same as the distance between I and K (the order of the tuples needs to be considered).

Returns the number of all boomerangs in the plane.

Example 1:

Input: points = [[0, 0), (1, 0), (2, 0]] output: 2: two maneuver dart for [[1, 0], [0, 0], [2, 0]] and [[1, 0], [2, 0], [0, 0]]Copy the code

Example 2:

Points = [[1,1],[2,2],[3,3]Copy the code

Example 3:

Input: points = [[1,1]] output: 0Copy the code

Tip:

N == points. Length 1 <= n <= 500 points[I]. Length == 2-10 ⁴ = xi, yi <= 10⁴

Related Topics

  • An array of
  • Hash table
  • mathematics
  • 👍 👎 0 195

Idea 1: Hash

  • The problem is hard to see at first time because it’s purely fanciful
  • But it’s easy to draw a picture of what you want, right
  • It’s just the number of combinations that are the same distance from any other point
  • Because you can switch them over as different solutions, so if there are m points that are the same distance from I, you can just say res = res + m times m minus 1.
  • To simplify distance calculation, distance squared can be used to represent distance, reducing the operation
  • Because the data bounds are small, you can ignore the bounds problem
  • Iterate over all the points and hash the key to the distance and value to the quantity
public int numberOfBoomerangs(int[][] points) {
    int res = 0, n = points.length;
    for (int i = 0; i < n; i++) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int l = 0; l < n; l++) {
            map.put(cal(points[i], points[l]), map.getOrDefault(cal(points[i], points[l]), 0) + 1);
        }
        for (int x : map.keySet()
        ) {
            res = res + map.get(x) * (map.get(x) - 1); }}return res;

}

public int cal(int[] l, int[] r) {
    int x = (r[0] - l[0]) * (r[0] - l[0]);
    int y = (r[1] - l[1]) * (r[1] - l[1]);
    return x + y;
}
Copy the code
  • Time complexity O(
    n 2 n^2     )
  • Time complexity O(
    n n     )