国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

LeetCode[296] Best Meeting Point

XUI / 3252人閱讀

摘要：投射法復雜度思路將二維數組上的點，分別映射到一維的坐標上。然后將兩個結果相加。代碼分別放到一維上來做復雜度思路分別建立行和列的數組，用來存放，在某一行，或者某一列，一共有多少人在這一個位置上。同理，來處理行的情況。

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;
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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 評論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

  • [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] 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

  • [Leetcode] Meeting Rooms 會議室

    摘要：排序法復雜度時間空間思路這題和很像，我們按開始時間把這些都給排序后，就挨個檢查是否有沖突就行了。有沖突的定義是開始時間小于之前最晚的結束時間。這里之前最晚的結束時間不一定是上一個的結束時間，所以我們更新的時候要取最大值。 Meeting Rooms Given an array of meeting time intervals consisting of start and end...

    jubincn 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<