05 August 2008
给定一个大小为 m x n 的 2D 整数网格和一个整数 x。在一个操作中，可以将 x 添加到网格中的任何元素或从其中减去 x。
单值网格是其中所有元素都相等的网格。
返回使网格单值的最小操作数。如果不可能，则返回-1。
Step 1. Add all the nums from the grid to an array
Step 2. Sort the array
Step 3. Find the sum and prefix sum of each num
Step 4. Now iterate through all the nums in the array, and calculate the cost, it only takes roughly O(1) to get the cost.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public int minOperations(int[][] grid, int x) {
int rows = grid.length;
int cols = grid[0].length;
int[] arr = new int[rows * cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
arr[i * cols + j] = grid[i][j];
}
}
Arrays.sort(arr);
int[] prefix = new int[arr.length];
int sum = arr[0];
for (int i = 1; i < arr.length; i++) {
if ((arr[i] - arr[i - 1]) % x != 0) {
return -1;
}
prefix[i] = prefix[i - 1] + arr[i - 1];
sum += arr[i];
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
int cur = sum - arr[i] * (arr.length - 2 * i) - (prefix[i] * 2);
if (cur <= min) {
min = cur;
} else {
return min / x;
}
}
return min / x;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int minOperations(int[][] grid, int x) {
List<Integer> results = new ArrayList<>();
for (int[] ints : grid) {
for (int j = 0; j < grid[0].length; j++) {
results.add(ints[j]);
}
}
Collections.sort(results);
int mid = (results.size()) / 2;
int ops = 0;
for (int[] ints : grid) {
for (int j = 0; j < grid[0].length; j++) {
int diff = Math.abs(ints[j] - results.get(mid));
if (diff % x != 0)
return -1;
else
ops += diff / x;
}
}
return ops;
}
}