資訊專欄INFORMATION COLUMN
摘要：投射法復(fù)雜度思路將二維數(shù)組上的點(diǎn)，分別映射到一維的坐標(biāo)上。然后將兩個(gè)結(jié)果相加。代碼分別放到一維上來(lái)做復(fù)雜度思路分別建立行和列的數(shù)組，用來(lái)存放，在某一行，或者某一列，一共有多少人在這一個(gè)位置上。同理，來(lái)處理行的情況。
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.
復(fù)雜度
O(MN), O(N)
思路
將二維數(shù)組上的點(diǎn)，分別映射到一維的坐標(biāo)上。然后將兩個(gè)結(jié)果相加。先考慮在一條直線上不同的點(diǎn)之間的最小距離值。再將所有的點(diǎ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);
}
}
}
// 分別放到一維上來(lái)做；
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
復(fù)雜度
O(MN),O(N)
思路
分別建立行和列的數(shù)組，用來(lái)存放，在某一行，或者某一列，一共有多少人在這一個(gè)位置上。
假設(shè)有m個(gè)人在i列上，有n個(gè)人在第j列上，那么最少能消掉Min(m,n)=k個(gè)人，并且他們travel的距離是，2 k (j - i) / 2 = k * (j - i)。
同理，來(lá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), 是這么多人走過(guò)的路
res += pair * (j - i);
// 要減去能消掉的人;
if((k[i] -= pair) == 0) i ++;
if((k[j] -= pair) == 0) j --;
}
}
return res;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65238.html
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 ...
摘要：為了盡量保證右邊的點(diǎn)向左走，左邊的點(diǎn)向右走，那我們就應(yīng)該去這些點(diǎn)中間的點(diǎn)作為交點(diǎn)。由于是曼哈頓距離，我們可以分開(kāi)計(jì)算橫坐標(biāo)和縱坐標(biāo)，結(jié)果是一樣的。 Best Meeting Point A group of two or more people wants to meet and minimize the total travel distance. You are given a ...
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 ...
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,...
摘要：排序法復(fù)雜度時(shí)間空間思路這題和很像，我們按開(kāi)始時(shí)間把這些都給排序后，就挨個(gè)檢查是否有沖突就行了。有沖突的定義是開(kāi)始時(shí)間小于之前最晚的結(jié)束時(shí)間。這里之前最晚的結(jié)束時(shí)間不一定是上一個(gè)的結(jié)束時(shí)間，所以我們更新的時(shí)候要取最大值。 Meeting Rooms Given an array of meeting time intervals consisting of start and end...
閱讀 1182·2021-11-19 09:40
閱讀 992·2021-11-12 10:36
閱讀 1297·2021-09-22 16:04
閱讀 3146·2021-09-09 11:39
閱讀 1297·2019-08-30 10:51
閱讀 1910·2019-08-30 10:48
閱讀 1251·2019-08-29 16:30
閱讀 501·2019-08-29 12:37
