曼哈顿距离：求解《距离顺序排列矩阵单元格》《找到最近的有相同 X 或 Y 坐标的点》

已知坐标，根据两点的曼哈顿距离排序，求解《距离顺序排列矩阵单元格》《找到最近的有相同 X 或 Y 坐标的点》

什么是曼哈顿距离（Manhattan Distance）

曼哈顿距离是两点在坐标系上的绝对轴距总和，上图红色线 点i坐标（x1, y1），点j坐标 (x2, y2)，点 i 到 点 j 的曼哈顿距离

d(i, j) = |x1 - y1| - |x2 - y2|

什么是欧几里得距离（Euclidian Distance）

欧几里得距离是两点间的直线距离，上图橙色线
欧几里得距离求解公式如下：

例题

1030. 距离顺序排列矩阵单元格

给定四个整数 row , cols , rCenter 和 cCenter 。有一个 rows x cols 的矩阵，你在单元格上的坐标是 (rCenter, cCenter) 。 返回矩阵中的所有单元格的坐标，并按与 (rCenter, cCenter) 的 距离 从最小到最大的顺序排。你可以按 任何 满足此条件的顺序返回答案。 单元格(r1, c1) 和 (r2, c2) 之间的距离为|r1 - r2| + |c1 - c2|。

答案

Sort

遍历，放入全部坐标，按距离起始点的曼哈顿（Manhattan Distance）升序排列

var allCellsDistOrder = function(rows, cols, rCenter, cCenter) {
  const ar = []
  for (let i = 0; i < rows; i++) 
    for (let j = 0; j < cols; j++) 
      ar.push([i, j])
  return ar.sort(([x1, y1], [x2, y2]) => Math.abs(x1 - rCenter) + Math.abs(y1 - cCenter) - Math.abs(x2 - rCenter) - Math.abs(y2 - cCenter))
};

桶排序

遍历，按曼哈顿距离（Manhattan Distance）分桶排序

var allCellsDistOrder = function(rows, cols, rCenter, cCenter) {
  const maxManhattanDistance = Math.max(rCenter, rows - 1 - rCenter) + Math.max(cCenter, cols - 1 - cCenter)
  const bucket = Array.from({length: maxManhattanDistance + 1}, _ => [])
  for (let i = 0; i < rows; i++)
    for (let j = 0; j < cols; j++)
      bucket[Math.abs(i - rCenter) + Math.abs(j - cCenter)].push([i, j])
  return bucket.flat()
};

广度优先搜索

var allCellsDistOrder = function(rows, cols, rCenter, cCenter) {
  const dr = [[-1, 0], [1, 0], [0, 1], [0, -1]], visited = new Set
  const queue = [[rCenter, cCenter]], r = []
  while (queue.length) {
    const [x1, y1] = queue.shift()
    if (visited.has(x1 * cols + y1)) continue
    r.push([x1, y1])
    visited.add(x1 * cols + y1)
    for (const [dx, dy] of dr) {
      const x2 = x1 + dx, y2 = y1 + dy
      if (x2 >= rows || x2 < 0 || y2 >= cols || y2 < 0) continue
      if (visited.has(x2 * cols + y2)) continue
      queue.push([x2, y2])
    }
  }
  return r
};

层序遍历

从起始点出发，每次向上一行，然后沿正菱形遍历

var allCellsDistOrder = function(rows, cols, rCenter, cCenter) {
  const dr = [[1, 1], [1, -1], [-1, -1], [-1, 1]], r = [[rCenter, cCenter]]
  const maxManhatanDistance = Math.max(rCenter, rows - 1 - rCenter) + Math.max(cCenter, cols - 1 - cCenter)
  let x = rCenter, y = cCenter
  for (let i = 1; i < maxManhatanDistance; i++) {
    x--
    for (let j = 0; j < dr.length; j++) {
      const [dx, dy] = dr[j]
      while (
        j === 0 && x !== rCenter ||
        j === 1 && y !== cCenter ||
        j === 2 && x !== rCenter ||
        j === 3 && y !== cCenter
      ) {
        if (x >= 0 && x < rows && y >= 0 && y < cols) r.push([x, y])
        x += dx, y += dy
      }
    }
  }
  return r
};

1779. 找到最近的有相同 X 或 Y 坐标的点

给你两个整数 x 和 y ，表示你在一个笛卡尔坐标系下的 (x, y) 处。同时，在同一个坐标系下给你一个数组 points ，其中 points[i] = [ai, bi] 表示在 (ai, bi) 处有一个点。当一个点与你所在的位置有相同的 x 坐标或者相同的 y 坐标时，我们称这个点是 有效的 。 给你两个整数 x 和 y ，表示你在一个笛卡尔坐标系下的 (x, y) 处。同时，在同一个坐标系下给你一个数组 points ，其中 points[i] = [ai, bi] 表示在 (ai, bi) 处有一个点。当一个点与你所在的位置有相同的 x 坐标或者相同的 y 坐标时，我们称这个点是 有效的 。 请返回距离你当前位置 曼哈顿距离 最近的 有效 点的下标（下标从 0 开始）。如果有多个最近的有效点，请返回下标 最小 的一个。如果没有有效点，请返回 -1 。 两个点 (x1, y1) 和 (x2, y2) 之间的 曼哈顿距离 为 abs(x1 - x2) + abs(y1 - y2) 。

答案

var nearestValidPoint = function(x, y, points) {
  const n = points.length
  let minManhattanDistance = Number.MAX_SAFE_INTEGER, minIndex = -1
  for (let i = 0; i < n; i++) {
    const [x1, y1] = points[i]
    if (x === x1 && y === y1) return i
    if (x === x1 || y === y1) {
      const manhattanDistance = Math.abs(x1 - x) + Math.abs(y1 - y)
      if (minManhattanDistance > manhattanDistance) {
        minManhattanDistance = manhattanDistance
        minIndex = i
      }
    }
  }
  return minIndex
};