[LeetCode] 296. Best Meeting Point

zzir 发布于2019-08-16 13:44 / 944人阅读

Problem

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Example:

Input: 

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 6 

Explanation: Given three people living at (0,0), (0,4), and (2,2):
             The point (0,2) is an ideal meeting point, as the total travel distance 
             of 2+2+2=6 is minimal. So return 6.

Solution

class Solution {
    public int minTotalDistance(int[][] grid) {
        List x = new ArrayList<>();
        List y = new ArrayList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    x.add(i);
                    y.add(j);
                }
            }
        }
        Collections.sort(x);
        Collections.sort(y);
        int i = 0, j = x.size()-1, res = 0;
        while (i < j) {
            res += (x.get(j)-x.get(i)+y.get(j)-y.get(i));
            i++; j--;
        }
        return res;
    }
}

云服务器 GPU云服务器 Meeting Best Point LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72257.html

LeetCode[296] Best Meeting Point

摘要：投射法复杂度思路将二维数组上的点，分别映射到一维的坐标上。然后将两个结果相加。代码分别放到一维上来做复杂度思路分别建立行和列的数组，用来存放，在某一行，或者某一列，一共有多少人在这一个位置上。同理，来处理行的情况。 LeetCode[296] Best Meeting Point A group of two or more people wants to meet and mini...

XUI 2019-08-14 15:01 评论0 收藏0
[Leetcode] Best Meeting Point 最佳见面点

摘要：为了尽量保证右边的点向左走，左边的点向右走，那我们就应该去这些点中间的点作为交点。由于是曼哈顿距离，我们可以分开计算横坐标和纵坐标，结果是一样的。 Best Meeting Point A group of two or more people wants to meet and minimize the total travel distance. You are given a ...

王军 2019-08-14 12:47 评论0 收藏0
[LintCode/LeetCode] Best Meeting Point

Problem A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance ...

morgan 2019-08-16 12:37 评论0 收藏0
[LeetCode] 253. Meeting Rooms II

Problem Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required. Example 1: Input: [[0, 30],[5,...

mengera88 2019-08-19 11:14 评论0 收藏0
[Leetcode] Meeting Rooms 会议室

摘要：排序法复杂度时间空间思路这题和很像，我们按开始时间把这些都给排序后，就挨个检查是否有冲突就行了。有冲突的定义是开始时间小于之前最晚的结束时间。这里之前最晚的结束时间不一定是上一个的结束时间，所以我们更新的时候要取最大值。 Meeting Rooms Given an array of meeting time intervals consisting of start and end...

jubincn 2019-08-14 12:47 评论0 收藏0