一刷 06/2022
Version #1 Divide and Conquer
Time The total runtime will be O(NlogN), where N = 2^n
Space O(N)
class Solution {
public int[] recoverArray(int n, int[] sums) {
// If we are adding a new element B to the existing set A1, A2,..., Ai
// We'll be doubling the set with new sums A1+B, A2+B,...,Ai+B
// So we want to get number B and partition the sums into two groups: with and without B
// How to decide B
// If all sums are positive, then the smallest sum (except for 0) is B itself
// If some sums are negative, then we'll know that the min sum is the sum of all negative numbers, and the second minimum sum is either sum of all negative numbers except for the largest negative number, or the sum of all negative numbers with the smallest positive number
// So if we do nums[1] - nums[0] we'll get either -x of a negative x, or x of a positive x
// We try both x = nums[1] - nums[0] and x = nums[0] - nums[1], and check if they are successfully partition the array
return recoverHelper(n, sums).stream().mapToInt(Integer::intValue).toArray();
}
private static int[] signs = new int[]{1, -1};
private List<Integer> recoverHelper(int n, int[] sums) {
if (sums == null) {
return new ArrayList<>();
}
if (n == 1) {
if (sums[1] != 0 && sums[0] != 0) {
return null;
}
// Only 1 number, it could be positive or negative
int num = sums[0] == 0 ? sums[1] : sums[0];
return new ArrayList<>(Arrays.asList(num));
}
Arrays.sort(sums);
List<Integer> result = null;
for (int sign : signs) {
int num = sign * (sums[1] - sums[0]);
int[] half = partition(num, sums);
if (half == null) {
continue;
}
// Can partition, go to the next layer
List<Integer> subResult = recoverHelper(n - 1, half);
if (subResult == null) {
continue;
}
result = new ArrayList<>();
result.add(num);
result.addAll(subResult);
}
return result;
}
private int[] partition(int num, int[] sums) {
int[] half = new int[sums.length / 2];
int i = 0;
Map<Integer, Integer> count = new HashMap<>();
for (int sum : sums) {
count.put(sum, count.getOrDefault(sum, 0) + 1);
}
// sums is sorted in ascending order
// If num < 0, we should start from the smallest numbers
// If num > 0, we should start from the largest numbers
int index = num > 0 ? sums.length - 1 : 0;
boolean hasZero = false;
while ((num > 0 && index >= 0) || (num <= 0 && index < sums.length)) {
int sum = sums[index];
if (count.getOrDefault(sum, 0) > 0) {
// If not exists, continue to the next element
int pair = sum - num;
count.put(sum, count.get(sum) - 1); // decrement the sum count by 1
if (!count.containsKey(pair) || count.get(pair) == 0) {
return null; // cannot partition
}
count.put(pair, count.get(pair) - 1);
half[i++] = pair;
if (pair == 0) {
hasZero = true;
}
}
//
if (num > 0) {
index--;
} else {
index++;
}
}
return hasZero ? half : null;
}
}
No comments:
Post a Comment