Brooke

一、題目

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,4]] Output: 2 Explanation: Of all the points, only [3,1], [2,4] and [4,4] are valid. Of the valid points, [2,4] and [4,4] have the smallest Manhattan distance from your current location, with a distance of 1. [2,4] has the smallest index, so return 2.

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.

Example 3:

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

 

Constraints:

• 1 <= points.length <= 104
• points[i].length == 2
• 1 <= x, y, ai, bi <= 104

 

二、程式作法

public class Solution
{
    public int NearestValidPoint(int x, int y, int[][] points)
    {
        int md = -1;
        int idx = 0;
        for (int i = 0; i < points.Length; i++)
        {
            if (points[i][0] == x && points[i][1] == y) return i;
            if (points[i][0] == x || points[i][1] == y)
            {
                if (md == -1)
                {
                    md = Math.Abs(x - points[i][0]) + Math.Abs(y - points[i][1]);
                    idx = i;
                }

                if (md != -1 && md > Math.Abs(x - points[i][0]) + Math.Abs(y - points[i][1]))
                {
                    md = Math.Abs(x - points[i][0]) + Math.Abs(y - points[i][1]);
                    idx = i;
                }
                else if (md != -1 && md == Math.Abs(x - points[i][0]) + Math.Abs(y - points[i][1]) && idx > i)
                    idx = i;
            }
        }

        if (md != -1) return idx;
        return md;
    }
}

 

public class Solution
{
    public int NearestValidPoint(int x, int y, int[][] points)
    {
        int minMd = (10000 - 1) * 2;
        int minIdx = -1;

        for (int i = 0; i < points.Length; i++)
        {
            if (points[i][0] == x || points[i][1] == y)
            {
                if (minMd > Math.Abs(x - points[i][0]) + Math.Abs(y - points[i][1]))
                {
                    minMd = Math.Abs(x - points[i][0]) + Math.Abs(y - points[i][1]);
                    minIdx = i;
                }
            }
        }

        return minIdx;
    }
}

 

三、思路筆記

這一題的英文意思一開始我真的看不懂，當中有去看其他人有做過這一題的文章後才了解，

題目要的是回傳合法座標中的最小 Manhattan distance 之最小的第一維(0-indexed)之索引值(此題目為二維索引)。

而什麼是合法的座標？就是陣列中的 x 座標或 y 座標值等於現在點的 x 座標或 y 座標值時就是合法座標。

做法為

1、先找出合法的座標有哪些？

2、找出合法座標中的最小 Manhattan distance

3、將該合法座標的第 i 個索引回傳