-
Notifications
You must be signed in to change notification settings - Fork 299
/
Problem_2035_PartitionArrayIntoTwoArraysToMinimizeSumDifference.java
58 lines (52 loc) · 1.72 KB
/
Problem_2035_PartitionArrayIntoTwoArraysToMinimizeSumDifference.java
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
55
56
57
58
package class45;
import java.util.HashMap;
import java.util.TreeSet;
public class Problem_2035_PartitionArrayIntoTwoArraysToMinimizeSumDifference {
public static int minimumDifference(int[] arr) {
int size = arr.length;
int half = size >> 1;
HashMap<Integer, TreeSet<Integer>> lmap = new HashMap<>();
process(arr, 0, half, 0, 0, lmap);
HashMap<Integer, TreeSet<Integer>> rmap = new HashMap<>();
process(arr, half, size, 0, 0, rmap);
int sum = 0;
for (int num : arr) {
sum += num;
}
int ans = Integer.MAX_VALUE;
for (int leftNum : lmap.keySet()) {
for (int leftSum : lmap.get(leftNum)) {
Integer rightSum = rmap.get(half - leftNum).floor((sum >> 1) - leftSum);
if (rightSum != null) {
int pickSum = leftSum + rightSum;
int restSum = sum - pickSum;
ans = Math.min(ans, restSum - pickSum);
}
}
}
return ans;
}
// arr -> 8 0 1 2 3 4 5 6 7
// process(arr, 0, 4) [0,4)
// process(arr, 4, 8) [4,8)
// arr[index....end-1]这个范围上,去做选择
// pick挑了几个数!
// sum挑的这些数,累加和是多少!
// map记录结果
// HashMap<Integer, TreeSet<Integer>> map
// key -> 挑了几个数,比如挑了3个数,但是形成累加和可能多个!
// value -> 有序表,都记下来!
// 整个过程,纯暴力!2^15 -> 3万多,纯暴力跑完,依然很快!
public static void process(int[] arr, int index, int end, int pick, int sum,
HashMap<Integer, TreeSet<Integer>> map) {
if (index == end) {
if (!map.containsKey(pick)) {
map.put(pick, new TreeSet<>());
}
map.get(pick).add(sum);
} else {
process(arr, index + 1, end, pick, sum, map);
process(arr, index + 1, end, pick + 1, sum + arr[index], map);
}
}
}