Li Kou daily question - day 31 -1779 Find the nearest point with the same X or Y coordinate

2022.6.29 Did you brush the questions today ？

---

subject ：

Here are two integers  x and  y , It means that you are in a Cartesian coordinate system  (x, y)  It's about . meanwhile , Give you an array in the same coordinate system  points , among  points[i] = [ai, bi]  It means that  (ai, bi)  There's a point in the middle . When a point has the same... As where you are x Coordinates or the same y Coordinates , We call this point Effective  .

Please return to your current position   Manhattan distance   Current   It works   Subscript of point （ Subscript from 0 Start ）. If there are multiple nearest valid points , Please return to subscript   Minimum   One of the . If it doesn't work , Please return  -1 .

Two points (x1, y1)  and (x2, y2)  Between Manhattan distance   by  abs(x1 - x2) + abs(y1 - y2) .

analysis ：

To give you one （x,y） And a two-dimensional array , You need to make sure that points and arrays are on a straight line , If meet , Find the smallest Manhattan distance , Then return to the first such minimum value in the array .

Ideas ： Traversing a two-dimensional array , Find the minimum , Update axis . If there are two equally small numbers , Only the first one is recorded

analysis ：

1. Violent solution

class Solution {
public:
    int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
        int res = 0;
        int ans = -1;
        int max = 1000000;
        for (auto i = 0; i < points.size(); i++)
        {
            if (points[i][0] == x || points[i][1] == y)
            {
                res = abs(points[i][0] - x) + abs(points[i][1]-y);
                if (res < max)
                {
                    max = res;
                    ans = i;
                }
            }


        }
        return ans;
    }
};