Pure Soul

  1. 首页
  2. 未分类
  3. 正文

Maximum Manhattan Distance of Two Points in Points Set

2024年4月1日 1907点热度 0人点赞 0条评论

Manhattan Distance


Definition: The Manhattan distance between two points (x_1, y_1) and (x_2, y_2) in a 2D plane is defined as dis = |x_1 - x_2| + |y_1 - y_2|, where | \cdot | denotes the absolute value.

Problem Definition


Given a set of points {p_1, p_2, \ldots, p_n}, where each point p_i is represented by its coordinates (x_i, y_i) in a 2D plane, the task is to find the maximum Manhattan distance between any two points p_a and p_b in the set. The desired time complexity for the solution is O(n).

Solution


To avoid the absolute value operation in the definition of Manhattan distance, we can consider different cases based on the relative positions of the points:

  • Case 1: dis_1 = x_1 - x_2 + y_1 - y_2, when x_1 > x_2 and y_1 > y_2
  • Case 2: dis_2 = x_2 - x_1 + y_1 - y_2, when x_1 and y_1 > y_2
  • Case 3: dis_3 = x_1 - x_2 + y_2 - y_1, when x_1 > x_2 and y_1
  • Case 4: dis_4 = x_2 - x_1 + y_2 - y_1, when x_1 and y_1

By simplifying these expressions, we can rewrite them as:

  • Simplified Case 1: dis_1 = (x_1 + y_1) - (x_2 + y_2)
  • Simplified Case 2: dis_2 = -(x_1 - y_1) - (x_2 - y_2)
  • Simplified Case 3: dis_3 = (x_1 - y_1) - (x_2 - y_2)
  • Simplified Case 4: dis_4 = -(x_1 + y_1) + (x_2 + y_2)

From these simplified cases, we can deduce that the maximum Manhattan distance can be obtained by considering the following scenarios:

  • The maximum value of (x+y) minus the minimum value of (x+y)
  • The minimum value of (x-y) minus the minimum value of (x-y)
  • The maximum value of (x-y) minus the minimum value of (x-y)
  • The minimum value of (x+y) minus the maximum value of (x+y)

By iterating through the set of points and calculating these values, we can find the maximum Manhattan distance in O(n) time complexity.

Here is Python code.

class Solution:
    def maxPoints(self, points):
        max_plus = max_minus = max_diff_plus = max_diff_minus = float('-inf')
        min_plus = min_minus = min_diff_plus = min_diff_minus = float('inf')
        max_plus_point = max_minus_point = max_diff_plus_point = max_diff_minus_point = None
        min_plus_point = min_minus_point = min_diff_plus_point = min_diff_minus_point = None

        for point in points:
            x, y = point
            if x + y > max_plus:
                max_plus = x + y
                max_plus_point = point
            if x + y < min_plus:
                min_plus = x + y
                min_plus_point = point
            if x - y > max_minus:
                max_minus = x - y
                max_minus_point = point
            if x - y < min_minus:
                min_minus = x - y
                min_minus_point = point
            if -x + y > max_diff_plus:
                max_diff_plus = -x + y
                max_diff_plus_point = point
            if -x + y < min_diff_plus:
                min_diff_plus = -x + y
                min_diff_plus_point = point
            if -x - y > max_diff_minus:
                max_diff_minus = -x - y
                max_diff_minus_point = point
            if -x - y < min_diff_minus:
                min_diff_minus = -x - y
                min_diff_minus_point = point

        distances = {
            (max_plus - min_plus): (max_plus_point, min_plus_point),
            (max_minus - min_minus): (max_minus_point, min_minus_point),
            (max_diff_plus - min_diff_plus): (max_diff_plus_point, min_diff_plus_point),
            (max_diff_minus - min_diff_minus): (max_diff_minus_point, min_diff_minus_point)
        }

        max_distance = max(distances.keys())
        return distances[max_distance], max_distance
标签: 暂无
最后更新:2024年4月1日

ycq

这个人很懒,什么都没留下

点赞
< 上一篇

COPYRIGHT © 2021 oo2ee.com. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS