|
6 | 6 |
|
7 | 7 | publicclass_296 { |
8 | 8 | publicstaticclassSolution1 { |
| 9 | +/** |
| 10 | + * Credit: https://leetcode.com/problems/best-meeting-point/solution/ Approach 3 |
| 11 | + */ |
9 | 12 | publicintminTotalDistance(int[][]grid) { |
10 | 13 | intm =grid.length; |
11 | 14 | intn =grid[0].length; |
12 | | - |
13 | | -List<Integer>I =newArrayList(m); |
14 | | -List<Integer>J =newArrayList(n); |
15 | | - |
| 15 | +List<Integer>rows =newArrayList<>(); |
| 16 | +List<Integer>cols =newArrayList<>(); |
16 | 17 | for (inti =0;i <m;i++) { |
17 | 18 | for (intj =0;j <n;j++) { |
18 | 19 | if (grid[i][j] ==1) { |
19 | | -I.add(i); |
20 | | -J.add(j); |
| 20 | +rows.add(i); |
| 21 | +cols.add(j); |
21 | 22 | } |
22 | 23 | } |
23 | 24 | } |
24 | | - |
25 | | -returngetMin(I) +getMin(J); |
| 25 | +introwMedian =rows.get(rows.size() /2); |
| 26 | +Collections.sort(cols); |
| 27 | +intcolMedian =cols.get(cols.size() /2); |
| 28 | +returnminDistance1D(rows,rowMedian) +minDistance1D(cols,colMedian); |
26 | 29 | } |
27 | 30 |
|
28 | | -privateintgetMin(List<Integer>list) { |
29 | | -intret =0; |
30 | | - |
31 | | -Collections.sort(list); |
32 | | - |
33 | | -inti =0; |
34 | | -intj =list.size() -1; |
35 | | -while (i <j) { |
36 | | -ret +=list.get(j--) -list.get(i++); |
| 31 | +privateintminDistance1D(List<Integer>points,intmedian) { |
| 32 | +intdistance =0; |
| 33 | +for (inti :points) { |
| 34 | +distance +=Math.abs(i -median); |
37 | 35 | } |
38 | | - |
39 | | -returnret; |
| 36 | +returndistance; |
40 | 37 | } |
| 38 | + |
41 | 39 | } |
42 | 40 | } |