算法数学算法

曼哈顿距离

字数统计: 1.9k字   |   阅读时长: 8分
, ,

摘要: 曼哈顿距离相关的几道题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在上一篇文章 通过分类讨论拆目标函数中的绝对值 中，我们看了一个比较简单的目标函数带绝对值的优化问题，目标函数的形式是下面这样：

本文我们看一下曼哈顿距离相关的问题，曼哈顿距离是一种距离度量方法，用于在二维平面上两点之间的距离计算，曼哈顿距离的公式与上面的形式非常类似，可以对比学习。

在二维的情况下，给定两个点 $P_{i} = (x_{i}, y_{i}), P_{j} = (x_{j}, y_{j})$，曼哈顿距离定义为：

下面我们看几个力扣中关于曼哈顿距离的题目。

$1 曼哈顿距离建模

题目

你在进行一个简化版的吃豆人游戏。你从 [0, 0] 点开始出发，你的目的地是 target = [xtarget, ytarget] 。地图上有一些阻碍者，以数组 ghosts 给出，第 i 个阻碍者从 ghosts[i] = [xi, yi] 出发。所有输入均为 整数坐标 。

每一回合，你和阻碍者们可以同时向东，西，南，北四个方向移动，每次可以移动到距离原位置 1 个单位 的新位置。当然，也可以选择 不动 。所有动作 同时 发生。

如果你可以在任何阻碍者抓住你 之前 到达目的地（阻碍者可以采取任意行动方式），则被视为逃脱成功。如果你和阻碍者 同时 到达了一个位置（包括目的地） 都不算 是逃脱成功。

如果不管阻碍者怎么移动都可以成功逃脱时，输出 true ；否则，输出 false 。

示例 1：
输入：ghosts = [[1,0],[0,3]], target = [0,1]
输出：true
解释：你可以直接一步到达目的地 (0,1) ，在 (1, 0) 或者 (0, 3) 位置的阻碍者都不可能抓住你。

示例 2：
输入：ghosts = [[1,0]], target = [2,0]
输出：false
解释：你需要走到位于 (2, 0) 的目的地，但是在 (1, 0) 的阻碍者位于你和目的地之间。

示例 3：
输入：ghosts = [[2,0]], target = [1,0]
输出：false
解释：阻碍者可以和你同时达到目的地。

提示：

1
2
3
4
5
6
1 <= ghosts.length <= 100
ghosts[i].length == 2
-1e4 <= xi, yi <= 1e4
同一位置可能有 多个阻碍者 。
target.length == 2
-1e4 <= xtarget, ytarget <= 1e4

算法：曼哈顿距离

人的起点到终点的曼哈顿距离需要小于所有鬼的起点到终点的曼哈顿距离，才能逃离。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
        int d0 = manhattan(0, 0, target[0], target[1]);
        for(vector<int>& g: ghosts)
        {
            if(manhattan(g[0], g[1], target[0], target[1]) <= d0)
                return false;
        }
        return true;
    }

private:
    int manhattan(int x1, int y1, int x2, int y2)
    {
        return abs(x1 - x2) + abs(y1 - y2);
    }
};

$2 从点集中选出曼哈顿距离最大的点对

给定一组点集，选出其中曼哈顿距离最大的点对。思路可以参考 拆目标函数中的绝对值。

一维曼哈顿距离拆绝对值

求 |f[i] - f[j]| 的最大值。

取两个方向上的最大值，相加。

两个方向对称，因此取两个方向上的最大值，相当于一个方向上同时找最大值和最小值。

二维曼哈顿距离拆绝对值

可能的计算有 4 种：

1
2
3
4
右上 - 左下
右下 - 左上
左上 - 右下
左下 - 右上

求 |f[i] - f[j]| + |g[i] - g[j]|。

找到四个方向上离 (0, 0) 最远的 4 个点。在四个方向上找最大值。也相当于在两个方向上同时找最大值和最小值。

三维曼哈顿距离拆绝对值

求 |f[i] - f[j]| + |g[i] - g[j]| + |h[i] - h[j]|

找到八个方向上离 (0, 0, 0) 最远的点。

1
2
3
4
5
6
7
8
1  1  1
1  1  -1
1  -1 1
1  -1 -1
-1 1  1
-1 1  -1
-1 -1 1
-1 -1 -1

也相当于四个方向上同时找最大值和最小值。

题目

给你两个长度相等的整数数组，返回下面表达式的最大值：

1
|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|

其中下标 i，j 满足 0 <= i, j < arr1.length。

示例 1：
输入：arr1 = [1,2,3,4], arr2 = [-1,4,5,6]
输出：13

示例 2：
输入：arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4]
输出：20

提示：

1
2
2 <= arr1.length == arr2.length <= 40000
-10^6 <= arr1[i], arr2[i] <= 10^6

算法：曼哈顿距离

一共 n 个点，每个点的位置为三维坐标 (arr1[i], arr2[i], i)。

三维中找曼哈顿距离最大的点对。

固定 z 维，在 (x, y) 的四个方向上取最大值和最小值。

代码(模板) (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
        int dx[4] = {-1, 1, -1, 1};
        int dy[4] = {-1, -1, 1, 1};
        int ans = 0;
        int n = arr1.size();
        for(int d = 0; d < 4; ++d)
        {
            int maxx = INT_MIN, minx = INT_MAX;
            for(int i = 0; i < n; ++i)
            {
                int x = arr1[i];
                int y = arr2[i];
                int z = i;
                maxx = max(maxx, x * dx[d]+ y * dy[d] + z);
                minx = min(minx, x * dx[d]+ y * dy[d] + z);
            }
            ans = max(ans, maxx - minx);
        }
        return ans;
    }
};

$3 选一点到点集所有点的最小曼哈顿距离和

给定一个点集，求到所有点的曼哈顿距离和最小的那个点。

题目

给你一个 m x n 的二进制网格 grid ，其中 1 表示某个朋友的家所处的位置。返回 最小的 总行走距离 。

总行走距离 是朋友们家到碰头地点的距离之和。

我们将使用 曼哈顿距离 来计算，其中 distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y| 。

提示:

1
2
3
4
5
m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] == 0 or 1.
grid 中 至少 有两个朋友

示例 1：
输入: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
输出: 6
解释: 给定的三个人分别住在(0,0)，(0,4) 和 (2,2):
(0,2) 是一个最佳的碰面点，其总行走距离为 2 + 2 + 2 = 6，最小，因此返回 6。

示例 2:
输入: grid = [[1,1]]
输出: 1

算法

最佳位置可以是多个，不一定唯一，其左边的元素和右边元素的个数相等。

用快速选择算法取两个方向的中位数即可。

用到类似结论的题目: 货仓选址与安排邮筒。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        if(grid.empty()) return 0;
        int n = grid.size(), m = grid[0].size();
        vector<int> xs, ys;
        vector<PII> persons;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(grid[i][j] == 1)
                {
                    xs.push_back(i);
                    ys.push_back(j);
                    persons.push_back(PII(i, j));
                }
            }
        int nx = xs.size();
        int ny = ys.size();
        nth_element(xs.begin(), xs.begin() + nx / 2, xs.end());
        int mid_x = *(xs.begin() + nx / 2);
        nth_element(ys.begin(), ys.begin() + ny / 2, ys.end());
        int mid_y = *(ys.begin() + ny / 2);
        int result = 0;
        for(PII person: persons)
            result += manhattan(person, mid_x, mid_y);
        return result;
    }

private:
    using PII = pair<int, int>;

    int manhattan(const PII& person, int i, int j)
    {
        return abs(person.first - i) + abs(person.second - j);
    }
};
Share