资讯专栏INFORMATION COLUMN

[LintCode/LeetCode] Best Meeting Point

morgan / 2346人阅读

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

Given three people living at (0,0), (0,4), and (2,2):

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

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
public class Solution {
    /**
     * @param grid: a 2D grid
     * @return: the minimize travel distance
     */
    public int minTotalDistance(int[][] grid) {
        // Write your code here
        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);
                }
            }
        }
        return getMD(x) + getMD(y);
    }
    public int getMD(List nums) {
        // zhong dian is here
        Collections.sort(nums);
        int i = 0, j = nums.size()-1;
        int distance = 0;
        while (i < j) {
            distance += nums.get(j--) - nums.get(i++);
        }
        return distance;
    }
}

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

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

相关文章

  • [LintCode/LeetCode] Meeting Rooms

    Problem Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings. Example Given intervals = [[0,30],[...

    Noodles 评论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 ...

    王军 评论0 收藏0
  • LeetCode[296] Best Meeting Point

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

    XUI 评论0 收藏0
  • [LeetCode] 296. 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 ...

    zzir 评论0 收藏0
  • [LintCode/LeetCode] Rotate Array

    Problem Given an array, rotate the array to the right by k steps, where k is non-negative. Example Example 1: Input: [1,2,3,4,5,6,7] and k = 3Output: [5,6,7,1,2,3,4]Explanation:rotate 1 steps to the r...

    chanthuang 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<