3

我有一个作业问题，我只能解决O(max(F)*N)（N大约10^5和F是10^9）复杂性，我希望你能帮助我。我得到N一组 4 个integer数字（名为S, F, a和b）；每组 4 个数字以这种方式描述一组数字：第一个连续的数字，从S包含的开始都在集合中。下一个b连续的数字不是，然后是下一个a数字，重复此操作，直到达到上限值F。例如对于S=5;F=50;a=1;b=19集合包含(5,25,45); S=1;F=10;a=2;b=1集合包含(1,2,4,5,7,8,10);

我需要找到包含在奇数个集合中的整数。保证对于给定的测试，只有 1 个符合此条件的数字。

我试图遍历和之间的每个数字min(S)并max(F)检查该数字包含多少组，如果它包含在奇数组中，那么这就是答案。正如我所说，以这种方式我得到了一个O (F*N)太多，而且我不知道如何查看一个数字是否在奇数组中。

如果您能帮助我，我将不胜感激。提前谢谢你，对不起我的英语和解释不好！

4

4 回答 4

3

暗示

我很想使用二分法。

选择一个值 x，然后计算所有集合中有多少个数字<=x。

如果这很奇怪，那么答案是 <=x，否则 >x。

这应该需要时间 O(Nlog(F))

替代解释

假设我们有集合

[S=1,F=8,a=2,b=1]->(1,2,4,5,7,8) 
[S=1,F=7,a=1,b=0]->(1,2,3,4,5,6,7) 
[S=6,F=8,a=1,b=1]->(6,8)

然后我们可以表：

N(y) = y 被包含在一个集合中的次数，

C(z) = sum(N(y) for y in range(1,z)) % 2

y  N(y)  C(z)
1  2     0
2  2     0
3  1     1
4  2     1
5  2     1
6  2     1
7  2     1
8  2     1

然后我们使用二分法找到 C(z) 变为 1 的第一个位置。

于 2012-05-09T18:31:35.120 回答
1

异或来救援。

从每个连续的集合中取出数字并将它们与结果集的内容进行异或。即，如果该号码当前标记为“存在”，则将其更改为“不存在”，反之亦然。

最后，您将在结果集中标记为存在的一个数字，该数字将出现奇数次。所有其他人将被异或偶数次，因此它们将回到原始状态。

至于复杂性，您只处理每个输入项一次，因此它基本上与输入项的总数成线性关系——至少假设您对结果集的操作是恒定的复杂性。至少如果我理解他们是如何措辞的，那似乎符合要求。

于 2012-05-10T02:26:02.420 回答
1

似乎找到一种方法来在这些集合上执行集合操作，特别是交集，而不必生成实际集合是很有用的。如果你能做到这一点，那么测试中所有这些集合的交集应该只剩下一个数字。撇开aandb部分不谈，很容易看出如何取包含 S 和 F 之间所有整数的两个集合的交集：交集就是 S=max(S1, S2) 和 F=min(F1 , F2)。

这给了你一个起点；现在你必须弄清楚如何创建两个集合的交集，考虑a和b。

于 2012-05-09T18:18:06.003 回答
0

听起来 S 被假定为非负数。鉴于您对时间边界的渴望，O(max(F)*N)您可以使用类似筛分的方法。

有一个整数数组，每个候选数字都有一个条目（即 min(S) 和 max(F) 之间的每个数字）。遍历所有四元组并将与每个四元组表示的包含数字关联的所有数组位置加 1。最后，查看数组以查看哪个计数是奇数。它所代表的数字就是满足你条件的数字。

这是有效的，因为您要进行 N 四倍，并且每个都需要 O(max(F)) 或更短的时间（假设 S 始终为非负数）来计算包含的数字。这给了你 O(max(F)*N)。

于 2012-05-09T18:41:10.900 回答