This is the 18th day of my participation in Gwen Challenge

describe

You are given two integers, x and y, which represent your current location on a Cartesian grid: (x, y). You are also given an array points where each points[i] = [ai, bi] represents that a point exists at (ai, bi). A point is valid if it shares the same x-coordinate or the same y-coordinate as your location.

Return the index (0-indexed) of the valid point with the smallest Manhattan distance from your current location. If there are multiple, return the valid point with the smallest index. If there are no valid points, return -1.

The Manhattan distance between two points (x1, y1) and (x2, y2) is abs(x1 – x2) + abs(y1 – y2).

Example 1:

Input: x = 3, y = 4, points = [[1, 2], [3, 1], [2, 4], [2, 3], [4]] Output: 2 Explanation: Of all the points, only [3,1], [2,4] and [4,4] are valid. [2,4] and [4,4] have the smallest Manhattan distance from your current location, With a distance of 1. [2,4] The smallest index, so return 2.Copy the code

Example 2:

Input: x = 3, y = 4, points = [[3,4]]
Output: 0
Explanation: The answer is allowed to be on the same location as your current location.
Copy the code

Example 3:

Input: x = 3, y = 4, points = [[2,3]]
Output: -1
Explanation: There are no valid points.
Copy the code

Note:

1 <= points.length <= 10^4
points[i].length == 2
1 <= x, y, ai, bi <= 10^4
Copy the code

parsing

(x,y) is the lowest index of the minimum Manhattan distance between (x,y) and (x,y). The idea is simple, and the answer can be obtained by directly traversing all the points.

answer

 class Solution(object):
    def nearestValidPoint(self, x, y, points):
        """
        :type x: int
        :type y: int
        :type points: List[List[int]]
        :rtype: int
        """
        result = -1
        distance = float('inf')
        for i in range(len(points)):
            point = points[i]
            xx, yy = point[0], point[1]
            if xx == x or yy == y:
                d = abs(xx-x)+abs(yy-y)
                if d < distance:
                    distance = d
                    result = i
        return result           	      
		
Copy the code

The results

Runtime: 608 ms, Given Python online submissions for Find Nearest Point That Has the Same X or Y Coordinate. Memory Usage: Submissions in Python online submissions for Find Nearest Point That Has the Same X or Y Coordinate.Copy the code

Original link: leetcode.com/problems/fi…

Your support is my biggest motivation