给定集合 {1, 2, 3, ... ,N}。我必须找到给定集合的子集的最大大小,以便子集中的任何 2 个数字的总和不能被给定的数字 K 整除。N 和 K 可以达到 2*10^9,所以我需要一个非常快的算法。我只想出了一个复杂度为 O(K) 的算法,它很慢。
Best Answer-推荐答案
首先计算所有的集合元素 mod k。然后解决简单的问题:
找到给定集合的子集的最大大小,使得子集中任意 2 个数字的总和不等于给定数字 K。
我将此集合分为两组(i和k-i),您不能同时选择set(i)和set(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
}
}
最后,您可以从元素 mod 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)。
为了获得更好的解决方案,您可以根据 mod k 对 myset 进行排序。
关于c++ - 不能被 K 整除的两个和的最大子集,我们在Stack Overflow上找到一个类似的问题:
https://stackoverflow.com/questions/14001634/
|