我需要找到给定集合{1,2,3,...,N}中最大的子集，使得该子集中任意两个数之和都不能被给定数字K整除。由于N和K可能达到2 * 10 ^ 9，所以我需要一个非常快的算法。我只想到了一个时间复杂度为O(K)的算法，速度很慢。
5个回答
5
首先，计算集合中所有元素 mod k 的值，并解决简单问题：找到给定集合中最大的子集大小，使得该子集中任意两个数的和不等于给定数字 K。
我将这个集合分成了两个集合（i 和 k-i），你不能同时选择集合 i 和集合 k-i。
int myset[]
int modclass[k]
for(int i=0; i< size of myset ;i++)
{
modclass[(myset[i] mod k)] ++;
}
选择
for(int i=0; i< k/2 ;i++)
{
if (modclass[i] > modclass[k-i])
{
choose all of the set elements that the element mod k equal i
}
else
{
choose all of the set elements that the element mod k equal k-i
}
}
最后，您可以添加一个元素，该元素模k等于0或k/2。
此解决方案的算法复杂度为O(K)。
您可以使用动态数组来改进此想法：
for(int i=0; i< size of myset ;i++)
{
x= myset[i] mod k;
set=false;
for(int j=0; j< size of newset ;j++)
{
if(newset[j][1]==x or newset[j][2]==x)
{
if (x < k/2)
{
newset[j][1]++;
set=true;
}
else
{
newset[j][2]++;
set=true;
}
}
}
if(set==false)
{
if (x < k/2)
{
newset.add(1,0);
}
else
{
newset.add(0,1);
}
}
}
现在你可以选择一个复杂度为O(myset.count)的算法。而你的算法复杂度大于O(myset.count)，因为你需要O(myset.count)来读取你的集合。 这个解决方案的复杂度是O(myset.count^2)，你可以根据输入选择算法，比较O(myset.count^2)和o(k)之间的区别。 对于更好的解决方案，你可以基于模k对myset进行排序。
- amin k
1
1看起来这是任意自然数集的一个解决方案。鉴于该集合是从1到N的数字，我相信可以基于仅涉及N和K的计算得出O(1)的解决方案。 - Patricia Shanahan
4
我假设这组数字始终是1到某个N。
考虑前N-(N mod K)个数字。形成 floor(N/K) 个由K个连续数字组成的序列，对于0至K-1的模数有缩减。对于每个组，floor(K/2) 必须被舍弃，因为它们的模数与另一个floor(K/2)子集的负模数相同。您可以从每组K个连续数字中保留ceiling(K/2)个。
现在考虑剩余的N mod K个数字。它们的模数从1开始。我还没有计算出确切的极限，但如果 N mod K 小于约 K/2，您将能够保留它们全部。否则，您将能够保留大约前 ceiling(K/2) 个。
==========================================================================
我认为这里的概念是正确的，但我还没有完全解决所有问题。
==========================================================================
以下是我对问题和答案的分析。 在接下来的内容中，| x | 表示 floor(x)。该解决方案类似于@Constantine答案中的解决方案，但在某些情况下有所不同。
考虑前 K * |N/K| 个元素。它们由模K的重复组成，重复了|N/K|次。
一般来说，我们可以包括 k (mod K) 的 |N/K| 个元素，但需要考虑以下限制：
如果 (k+k)%K 为零，则只能包括一个 k (mod K) 元素。对于k=0和k=(K/2)%K的情况是如此，这仅适用于偶数K。
这意味着我们从重复项中获得 |N/K| * |(K-1)/2| 个元素。
我们需要纠正省略的元素。如果 N >= K，则需要添加一个0 mod K元素。如果K是偶数且N> = K/2，则还需要添加(K/2)%K元素。
最后，如果 M(N)!=0，则需要添加一个部分或完整的重复元素，min(N%K,|(K-1)/2|)。
最终公式是：
考虑前N-(N mod K)个数字。形成 floor(N/K) 个由K个连续数字组成的序列，对于0至K-1的模数有缩减。对于每个组，floor(K/2) 必须被舍弃，因为它们的模数与另一个floor(K/2)子集的负模数相同。您可以从每组K个连续数字中保留ceiling(K/2)个。
现在考虑剩余的N mod K个数字。它们的模数从1开始。我还没有计算出确切的极限，但如果 N mod K 小于约 K/2，您将能够保留它们全部。否则，您将能够保留大约前 ceiling(K/2) 个。
==========================================================================
我认为这里的概念是正确的，但我还没有完全解决所有问题。
==========================================================================
以下是我对问题和答案的分析。 在接下来的内容中，| x | 表示 floor(x)。该解决方案类似于@Constantine答案中的解决方案，但在某些情况下有所不同。
考虑前 K * |N/K| 个元素。它们由模K的重复组成，重复了|N/K|次。
一般来说，我们可以包括 k (mod K) 的 |N/K| 个元素，但需要考虑以下限制：
如果 (k+k)%K 为零，则只能包括一个 k (mod K) 元素。对于k=0和k=(K/2)%K的情况是如此，这仅适用于偶数K。
这意味着我们从重复项中获得 |N/K| * |(K-1)/2| 个元素。
我们需要纠正省略的元素。如果 N >= K，则需要添加一个0 mod K元素。如果K是偶数且N> = K/2，则还需要添加(K/2)%K元素。
最后，如果 M(N)!=0，则需要添加一个部分或完整的重复元素，min(N%K,|(K-1)/2|)。
最终公式是：
|N/K| * |(K-1)/2| +
(N>=K ? 1 : 0) +
((N>=K/2 && (K%2)==0) ? 1 : 0) +
min(N%K,|(K-1)/2|)
这与@Constantine的版本在某些情况下甚至涉及K都有所不同。例如，考虑N=4，K=6。正确答案是3，即集合{1, 2, 3}的大小。@Constantine的公式给出|(6-1)/2|=|5/2|=2。上面的公式从前两行得到0，在第三行得到1，在最后一行得到2，得出了正确的答案。
- Patricia Shanahan
2
我无法完全想明白它，但我猜你的解决方案是正确的，我会给它投赞成票。但是你的解决方案不能将元素发送到输出。 - amin k
@amink 谢谢你的支持。问题说的是“找到一个子集的最大大小”，而不是“找到最大的子集”，所以我并没有试图生成这个子集，只是计算它的大小。问题还要求快速解决。我的解决方案是 O(1)。任何生成该集合的解决方案在 K>1 时都是 \Omega(N)。 - Patricia Shanahan
3
公式是：
|N/K| * |(K-1)/2| + ost
ost =
if n<k:
ost =0
else if n%k ==0 :
ost =1
else if n%k < |(K-1)/2| :
ost = n%k
else:
ost = |(K-1)/2|
where |a/b|，例如 |9/2| = 4 |7/2| = 3
举例说明：n = 30，k = 7;
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
1 2 3 |4| 5 6 7 - 这是第一行。 8 9 10 |11| 12 13 14 - 这是第二行。 如果我们每行获取前3个数字，就可以得到这个子集的大小。此外，我们可以从 (7 14 28) 中再添加一个数字。
获取前3个数字（1 2 3）是一个数字 |(k-1)/2| 。该行的数字数目为 |n/k|。 如果没有余数，我们可以添加一个数字（例如最后一个数字）。 如果余数 < |(k-1)/2|，我们获取最后一行中所有数字， 否则获取 |(K-1)/2|。
感谢注意特殊情况。 当 k>n 时， ost = 0。
- Constantine Kuznetsov
2
1我认为公式是正确的。如果有一些解释，答案会更好。 - Patricia Shanahan
1经过进一步思考，我认为它未能考虑到在K为偶数时包括K/2的一个副本。例如，对于N=4、K=6，它的答案是2。正确答案是3，即集合{1, 2, 3}的大小。请参见我的分析答案。 - Patricia Shanahan
0
n,k=(raw_input().split(' '))
n=int(n)
k=int(k)
l=[0 for x in range(k)]
d=[int(x) for x in raw_input().split(' ')]
flag=0
for x in d:
l[x%k]=l[x%k]+1
sum=0
if l[0]!=0:
sum+=1
if (k%2==0):
sum+=1
if k==1:
print 1
elif k==2:
print 2
else:
i=1
j=k-1
while i<j:
sum=sum+(l[i] if l[i]>=l[j] else l[j])
i=i+1
j=j-1
print sum
- Abrar Khan
2
2你能否解释一下为什么这个答案适合这个问题？ - Taegost
1尽管这段代码可能有助于解决问题，但提供关于它为什么以及如何回答问题的额外上下文会显著提高其长期价值。请编辑您的答案以添加一些解释。 - Toby Speight
0
这是对ABRAR TYAGI和amin k解决方案的解释。
该解决方案的方法是：
- 创建具有K个桶的数组L，并将输入数组D中的所有元素分组到K个桶中。每个桶L[i]包含D的元素，使得（元素％K）= i。
- 所有单独可被K整除的元素都在L [0]中。因此，只有其中一个元素（如果有）可以属于我们的最终（最大）子集。任何两个这些元素的总和都是可被K整除的。
- 如果我们将L [i]中的一个元素添加到L [K-i]中的一个元素，则它们的总和可被K整除。因此，我们只能从这些桶中选择一个桶来添加元素到我们的最终集合中。我们选择最大的桶。
代码： d是包含大小为n的初始数字集的数组。此代码的目标是找到d的最大子集的计数，使得没有两个整数的和可被2整除。
l是将数组d中的每个（元素）减少为（元素％k）并保存其出现频率的数组。
例如，l [1] 包含所有元素的频率 % k = 1我们知道 1 + (k-1) % k = 0，因此要满足没有两个数字的和 % k 应该为 0 的条件，必须放弃 l [1] 或 l [k-1] 中的一个。
但是，由于我们需要 d 的最大子集，因此选择 l [1] 和 l [k-1] 中较大的那个。
我们循环遍历数组 l，使得对于 (i=1; i<=k/2 && i有两个离群值。l [0] 组中任意两个数字的和 % k = 0。因此，如果 l [0] 不为零，则加 1。
如果 k 是偶数，则循环不处理 i=k/2，并使用与上述相同的逻辑将计数增加一。
- smumm
1
这是对 @ABRAR TYAGI 和 amin k 解决方案的说明。 - smumm
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接