LeetCode[296] Best Meeting Point

XUI 发布于2019-08-14 15:01 / 3198人阅读

摘要：投射法复杂度思路将二维数组上的点，分别映射到一维的坐标上。然后将两个结果相加。代码分别放到一维上来做复杂度思路分别建立行和列的数组，用来存放，在某一行，或者某一列，一共有多少人在这一个位置上。同理，来处理行的情况。

LeetCode[296] 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(MN), O(N)

思路
将二维数组上的点，分别映射到一维的坐标上。然后将两个结果相加。先考虑在一条直线上不同的点之间的最小距离值。再将所有的点映射到一条纵线上，考虑他们之间的距离的最小值。

代码

// O(MN)
public int minTotalDistance(int[][] grid) {
    // means which row has the people on it
    List row = new LinkedList<>();
    // means which col has the people on it
    List col = new LinkedList<>();
    for(int i = 0; i< grid.length; i ++) {
        for(int j = 0; j < grid[0].length; j ++) {
            if(grid[i][j] == 1) {
                row.add(i);
                col.add(j);
            }
        }
    }
    // 分别放到一维上来做；
    return getMin(row) + getMin(col);
}

public int getMin(List list) {
    int res = 0;
    Collections.sort(list);
    int i = 0, j = list.size() - 1;
    while(i < j) {
        res += list.get(j --) - list.get(i ++);
    }
    return res;
}

Bucket Sort

复杂度
O(MN),O(N)

思路
分别建立行和列的数组，用来存放，在某一行，或者某一列，一共有多少人在这一个位置上。
假设有m个人在i列上，有n个人在第j列上，那么最少能消掉Min(m,n)=k个人，并且他们travel的距离是，2 k (j - i) / 2 = k * (j - i)。
同理，来处理行的情况。

代码

public int minTotalDistance(int[][] grid) {
    int[] row = new int[grid.length];
    int[] col = new int[grid[0].length];
    for(int i = 0; i < grid.length; i ++) {
        for(int j = 0; j < grid[0].length; j ++) {
            if(grid[i][j] == 1) {
                ++ row[i];
                ++ col[j];
            }
        }
    }
    int res = 0;
    for(int[] k : new int[][]{row, col}) {
        int i = 0, j = k.length - 1;
        while(i < j) {
            // 在i,和j位置分别有多少人，取最小的人作为能消去的最少的人
            int pair = Math.min(k[i], k[j]);
            // (j - i) / 2 * 2 pair = pair * (j - i), 是这么多人走过的路
            res += pair * (j - i);
            // 要减去能消掉的人;
            if((k[i] -= pair) == 0) i ++;
            if((k[j] -= pair) == 0) j --;
        }
    }
    return res;
}

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

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

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

[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 2019-08-16 13:44 评论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