资讯专栏INFORMATION COLUMN

[Leetcode] Best Meeting Point 最佳见面点

王军 / 2956人阅读

摘要:为了尽量保证右边的点向左走,左边的点向右走,那我们就应该去这些点中间的点作为交点。由于是曼哈顿距离,我们可以分开计算横坐标和纵坐标,结果是一样的。

Best Meeting Point

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|.

For 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.

横纵分离 复杂度

时间 O(NM) 空间 O(NM)

思路

为了保证总长度最小,我们只要保证每条路径尽量不要重复就行了,比如1->2->3<-4这种一维的情况,如果起点是1,2和4,那2->31->2->3这两条路径就有重复了。为了尽量保证右边的点向左走,左边的点向右走,那我们就应该去这些点中间的点作为交点。由于是曼哈顿距离,我们可以分开计算横坐标和纵坐标,结果是一样的。所以我们算出各个横坐标到中点横坐标的距离,加上各个纵坐标到中点纵坐标的距离,就是结果了。

代码
public class Solution {
    public int minTotalDistance(int[][] grid) {
        List ipos = new ArrayList();
        List jpos = new ArrayList();
        // 统计出有哪些横纵坐标
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 1){
                    ipos.add(i);
                    jpos.add(j);
                }
            }
        }
        int sum = 0;
        // 计算纵坐标到纵坐标中点的距离,这里不需要排序,因为之前统计时是按照i的顺序
        for(Integer pos : ipos){
            sum += Math.abs(pos - ipos.get(ipos.size() / 2));
        }
        // 计算横坐标到横坐标中点的距离,这里需要排序,因为统计不是按照j的顺序
        Collections.sort(jpos);
        for(Integer pos : jpos){
            sum += Math.abs(pos - jpos.get(jpos.size() / 2));
        }
        return sum;
    }
}

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

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

相关文章

  • 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
  • [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 评论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
  • [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 评论0 收藏0
  • Best Time To Buy And Sell Stock 买卖股票最佳时机

    摘要:关键字,,算法,,动态规划,上关于主题的题目有四个这四个题目难度依次递增。其中第四个问题是寻求一个通解,在给定和最大买卖次数的情况下,求最大收益。首先大致的解题方向是动态规划,这个应该不难想到。之后就是怎么找到状态,怎么列状态转移方程。 关键字:leetcode,Best Time To Buy And Sell Stock,算法,algorithm,动态规划,dynamic prog...

    elliott_hu 评论0 收藏0

发表评论

0条评论

王军

|高级讲师

TA的文章

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