题目描述
给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组，分别求出两个数组的和，并 最小化 两个数组和之 差的绝对值 。nums 中每个元素都需要放入两个数组之一。
请你返回 最小 的数组和之差。
示例 1：
输入：nums = [3,9,7,3]
输出：2
解释：最优分组方案是分成 [3,9] 和 [7,3] 。
数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。
示例 2：
输入：nums = [-36,36]
输出：72
解释：最优分组方案是分成 [-36] 和 [36] 。
数组和之差的绝对值为 abs((-36) - (36)) = 72 。
示例 3：
输入：nums = [2,-1,0,4,-2,-9]
输出：0
解释：最优分组方案是分成 [2,4,-9] 和 [-1,0,-2] 。
数组和之差的绝对值为 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。
提示：
1 <= n <= 15nums.length == 2 * n-107 <= nums[i] <= 107
解法
方法一
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
33
34
35
36
37 | class Solution:
def minimumDifference(self, nums: List[int]) -> int:
n = len(nums) >> 1
f = defaultdict(set)
g = defaultdict(set)
for i in range(1 << n):
s = cnt = 0
s1 = cnt1 = 0
for j in range(n):
if (i & (1 << j)) != 0:
s += nums[j]
cnt += 1
s1 += nums[n + j]
cnt1 += 1
else:
s -= nums[j]
s1 -= nums[n + j]
f[cnt].add(s)
g[cnt1].add(s1)
ans = inf
for i in range(n + 1):
fi, gi = sorted(list(f[i])), sorted(list(g[n - i]))
# min(abs(f[i] + g[n - i]))
for a in fi:
left, right = 0, len(gi) - 1
b = -a
while left < right:
mid = (left + right) >> 1
if gi[mid] >= b:
right = mid
else:
left = mid + 1
ans = min(ans, abs(a + gi[left]))
if left > 0:
ans = min(ans, abs(a + gi[left - 1]))
return ans
|
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 | class Solution {
public int minimumDifference(int[] nums) {
int n = nums.length >> 1;
Map<Integer, Set<Integer>> f = new HashMap<>();
Map<Integer, Set<Integer>> g = new HashMap<>();
for (int i = 0; i < (1 << n); ++i) {
int s = 0, cnt = 0;
int s1 = 0, cnt1 = 0;
for (int j = 0; j < n; ++j) {
if ((i & (1 << j)) != 0) {
s += nums[j];
++cnt;
s1 += nums[n + j];
++cnt1;
} else {
s -= nums[j];
s1 -= nums[n + j];
}
}
f.computeIfAbsent(cnt, k -> new HashSet<>()).add(s);
g.computeIfAbsent(cnt1, k -> new HashSet<>()).add(s1);
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i <= n; ++i) {
List<Integer> fi = new ArrayList<>(f.get(i));
List<Integer> gi = new ArrayList<>(g.get(n - i));
Collections.sort(fi);
Collections.sort(gi);
for (int a : fi) {
int left = 0, right = gi.size() - 1;
int b = -a;
while (left < right) {
int mid = (left + right) >> 1;
if (gi.get(mid) >= b) {
right = mid;
} else {
left = mid + 1;
}
}
ans = Math.min(ans, Math.abs(a + gi.get(left)));
if (left > 0) {
ans = Math.min(ans, Math.abs(a + gi.get(left - 1)));
}
}
}
return ans;
}
}
|
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
33
34
35
36
37
38
39
40
41
42
43
44
45 | class Solution {
public:
int minimumDifference(vector<int>& nums) {
int n = nums.size() >> 1;
vector<vector<int>> f(n + 1), g(n + 1);
for (int i = 0; i < (1 << n); ++i) {
int s = 0, cnt = 0;
int s1 = 0, cnt1 = 0;
for (int j = 0; j < n; ++j) {
if (i & (1 << j)) {
s += nums[j];
++cnt;
s1 += nums[n + j];
++cnt1;
} else {
s -= nums[j];
s1 -= nums[n + j];
}
}
f[cnt].push_back(s);
g[cnt1].push_back(s1);
}
for (int i = 0; i <= n; ++i) {
sort(f[i].begin(), f[i].end());
sort(g[i].begin(), g[i].end());
}
int ans = INT_MAX;
for (int i = 0; i <= n; ++i) {
for (int a : f[i]) {
int left = 0, right = g[n - i].size() - 1;
int b = -a;
while (left < right) {
int mid = (left + right) >> 1;
if (g[n - i][mid] >= b)
right = mid;
else
left = mid + 1;
}
ans = min(ans, abs(a + g[n - i][left]));
if (left > 0) ans = min(ans, abs(a + g[n - i][left - 1]));
}
}
return ans;
}
};
|
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54 | func minimumDifference(nums []int) int {
n := len(nums) >> 1
f := make([][]int, n+1)
g := make([][]int, n+1)
for i := 0; i < (1 << n); i++ {
s, cnt := 0, 0
s1, cnt1 := 0, 0
for j := 0; j < n; j++ {
if (i & (1 << j)) != 0 {
s += nums[j]
cnt++
s1 += nums[n+j]
cnt1++
} else {
s -= nums[j]
s1 -= nums[n+j]
}
}
f[cnt] = append(f[cnt], s)
g[cnt1] = append(g[cnt1], s1)
}
for i := 0; i <= n; i++ {
sort.Ints(f[i])
sort.Ints(g[i])
}
ans := 1 << 30
for i := 0; i <= n; i++ {
for _, a := range f[i] {
left, right := 0, len(g[n-i])-1
b := -a
for left < right {
mid := (left + right) >> 1
if g[n-i][mid] >= b {
right = mid
} else {
left = mid + 1
}
}
ans = min(ans, abs(a+g[n-i][left]))
if left > 0 {
ans = min(ans, abs(a+g[n-i][left-1]))
}
}
}
return ans
}
func abs(x int) int {
if x > 0 {
return x
}
return -x
}
|