我有一个数字数组，比如[1,2,3,11000]，现在我想得到这个数组的所有可能组合，并计算它的和。组合是有效的，使得两个组合具有不同的元素子集。然后按降序排列所有和值，得到前k个元素。
示例：
[1,2,3,1,1000]
组合：
较早的重复会被三振，例如(3,1)与较早的(1,3)匹配。
()，(1)，(2)，(3)，(1)，(1000)，(1,2)，(1,3(2,11000)，(3,11000)，(1,2,3,1)，(1,23,1000)，(1,3,11000)，(2,3,11000)，(1,2,3,11000)
以及相应的总和：
0，1，2，3，1，1000，3，4，2，1001，5，4，1003，1001>，6，4，1003、5，1004、1002，61005，1003，11006，1007
Getting top k=3, sums = 1007, 1006, 1005
So output is [1007, 1006, 1005].
限制：
- 阵列大小n=1到105
- 阵列元素-109到109
- k的范围从1到2000
这是我的代码，参考来自这里：
static List<Long> printDistSum(int arr[]) {
List<Long> list = new ArrayList<>();
int n = arr.length;
// There are totoal 2^n subsets
long total = (long) Math.pow(2, n);
// Consider all numbers from 0 to 2^n - 1
for (int i = 0; i < total; i++) {
long sum = 0;
// Consider binary representation of
// current i to decide which elements
// to pick.
for (int j = 0; j < n; j++)
if ((i & (1 << j)) != 0)
sum += arr[j];
// Print sum of picked elements.
list.add(sum);
}
return list;
}
此代码适用于小范围的输入，但适用于大范围的输入。如何解决此程序。
我可能有足够好的解决方案。它具有时间复杂性O(n*k*log(k))。
首先我们需要计算所有正值的最大和。
接下来，我们需要对正值进行迭代，从最小值到最大值。对于这些值中的每一个，我们计算新组合的和(在开始时，我们有一个最大和的组合)。新的组合不会包含给定的值，所以我们需要从和中减去它。
最后，我们需要对负值进行迭代。这些值不属于上一步的组合，所以我们需要将这些值添加到和中。
在每次迭代中只需要k个最大和。我使用优先级队列来存储这些总和。该类使用堆数据结构，因此添加/删除值具有对数时间。
代码：
private static long[] findSums(int[] array, int k) {
long maxSum = Arrays.stream(array).filter(it -> it >= 0).sum();
int[] positives = Arrays.stream(array).filter(it -> it >= 0).sorted().toArray();
int[] negatives = Arrays.stream(array).filter(it -> it < 0).sorted().toArray();
// sort time complexity is O(n*log(n))
PriorityQueue<Long> sums = new PriorityQueue<>(k); // priority queue is implemented using heap so adding element has time complexity O(log(n))
sums.add(maxSum); // we start with max sum - combination of all positive elements
int previous = Integer.MIN_VALUE;
Long[] previousAddedSums = {};
Long[] sumsToIterate;
// iterate over positive values
for (int i = 0; i < positives.length; i++) {
if (positives[i] == previous) {
sumsToIterate = previousAddedSums;
} else {
sumsToIterate = sums.toArray(new Long[sums.size()]);
}
previousAddedSums = new Long[sumsToIterate.length];
for (int j = 0; j < sumsToIterate.length; j++) {
long newSum = sumsToIterate[j] - positives[i];
// new sum is calculated - value positives[i] is removed from combination (subtracted from sum of that combination)
sums.add(newSum);
previousAddedSums[j] = newSum;
if (sums.size() > k) {
sums.poll(); // only first k maximum sums are needed at the moment
}
}
previous = positives[i];
}
previous = Integer.MAX_VALUE;
// iterate over negative values in reverse order
for (int i = negatives.length - 1; i >= 0; i--) {
if (negatives[i] == previous) {
sumsToIterate = previousAddedSums;
} else {
sumsToIterate = sums.toArray(new Long[sums.size()]);
}
previousAddedSums = new Long[sumsToIterate.length];
for (int j = 0; j < sumsToIterate.length; j++) {
long newSum = sumsToIterate[j] + negatives[i]; // value negatives[i] is added to combination (added to sum of that combination)
sums.add(newSum);
previousAddedSums[j] = newSum;
if (sums.size() > k) {
sums.poll();
}
}
previous = negatives[i];
}
long[] result = new long[sums.size()];
for (int i = sums.size() - 1; i >=0 ; i--) {
result[i] = sums.poll();
}
// get sums from priority queue in proper order
return result;
// this whole method has time complexity O(n * k * log(k))
// k is less than or equal 2000 so it should be good enough ;)
}
演示：https://ideone.com/yf6POI
编辑：我已经修复了我的解决方案。我检查当前值是否和以前的值相同，而不是迭代不同的值。在这种情况下，我使用上一步创建的组合(和)。这样可以防止创建组合的重复项。
如果我解释得不够好，我很抱歉。我没有用英语描述算法/数学的经验。
请忽略之前的所有帖子，因为它们都是错误的。直觉上，我们必须使用回溯来找到所有想要的组合，但不可能在10^5元素上回溯。
约束1<=n<=10^5暗示我们的算法被O(nlogn)排序瓶颈
约束1<=k<=min(2000,2^n)暗示我们可以回溯k个元素，因为k小于11。2^11＝2024/log(2000)＝11——实际上；2^n"；提供解决方案：)
我的算法(nlog(n)+2^k)
- 对数组进行排序
- 记录所有正整数之和的最高分数组合
- 在math.min(log(k)——小于11，n)个元素的排序数组中找到一个窗口——最坏的情况是，这个窗口由排序数组中最低的11个绝对值。几种方法做到这一点，因为候选人必须在22个要素内窗口(11个最小正值+11个最大负值)，我们可以使用大小为11的PriorityQueue扫描这22个元素。或我们可以使用两个指针来找到大小为11的滑动窗口
- 回溯这个11个绝对值元素窗口，找到每个组合的和，并将它们放入一个大小为k/k-1的PriorityQueue中。(k代表没有积极因素的情况)
- 结果是所有正整数的和加(PriorityQueue中k-1个元素的总和)
昨天我也被问到了同样的问题，但遗憾的是我昨天没能解决。我今天试着解决了这个问题，今天我想我已经找到了答案。
首先，我不认为不同的子集意味着集合中的不同成本，即在[1，2，1]的数组中，两个子集都是有效的=>[1，2，3]和[2，3，1]，因为它们都使用不同的1。现在我的解决方案是牢记这一点。但若您真的想在集合中保留不同的元素，那个么您可以简单地移除多个元素，然后进行partial_sort。
逻辑
- 将所有+ve个数的和存储在一个变量中，比如maxsum
- 将负数转换为其绝对值
- 按排序顺序获取最低的最小(k-1，n)个元素
- 找到它们的所有组合，并从最大和中减去它们
- 在找到它们的所有组合时，我们只需要最低的k-1组合。因此，我们必须找到一种方法来保持组合的数量不变。为此，使用排序的数据结构并将其大小限制为k，然后对于排序数组中的每个元素，遍历组合框，并在该数据结构的结束元素较大的情况下将这些组合框添加到排序数据结构中。然后也弹出结束元素
- 为了解决上述问题，我使用了2个向量，因为顺序已经保持排序
所提出的解决方案的时间复杂度为O(n*log(k)+k^2)。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;
template <class T>
void print(vector<T> topSumm)
{
for (ll itr : topSumm)
cout << itr << 't';
cout << 'n';
}
vector<ll> mergeSortedArrays(vector<ll> &minns, vector<ll> &temp)
{
vector<ll> ans(minns.size() + temp.size());
int i{0}, j{0}, k{0};
while (i < minns.size() && j < temp.size())
{
if (temp[j] < minns[i])
ans[k++] = temp[j++];
else
ans[k++] = minns[i++];
}
while (i < minns.size())
ans[k++] = minns[i++];
while (j < temp.size())
ans[k++] = temp[j++];
return ans;
}
vector<ll> topKSum(vector<int> &arr, int k)
{
int n{(int)arr.size()};
ll maxSumm{0};
for (int i{0}; i < n; ++i)
{
if (arr[i] > 0)
maxSumm += arr[i];
else
arr[i] = -arr[i];
}
int nk{min(k - 1, n)};
partial_sort(arr.begin(), arr.begin() + nk, arr.end());
vector<ll> minns{0, maxSumm};
ll summ{};
bool breakOuter{false};
for (int i{0}; i < nk; ++i)
{
vector<ll> temp;
for (ll nums : minns)
{
summ = nums + arr[i];
if (minns.size() + temp.size() < k)
temp.push_back(summ);
else
{
if (minns.back() > summ)
{
minns.pop_back();
temp.push_back(summ);
}
else
{
if (nums == 0)
breakOuter = true;
break;
}
}
}
if (breakOuter)
break;
minns = mergeSortedArrays(minns, temp);
}
vector<ll> ans(k);
int i{0};
for (ll nums : minns)
ans[i++] = maxSumm - nums;
return ans;
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
vector<int> arr(n);
ll maxSumm{0};
for (int i{0}; i < n; ++i)
cin >> arr[i];
vector<ll> topSums = topKSum(arr, k);
print<ll>(topSums);
}
return 0;
}