求一道NOIP难度题的线性空间复杂度,常数时间复杂度的算法……

发布网友 发布时间：2022-04-23 06:36

我来回答

共3个回答

热心网友 时间：2022-06-04 02:48

时间复杂度O(n)的算法肯定是有的，但不知道楼主是想知道理论结果还是想解决实际问题？
比如下面的算法理论上是行，时间和空间复杂度都是O(n)，但实际操作32位数肯定是不行，存储不够：
用一个bit表示一个数，总共需要k^32个bit（假定n是32位k进制数，你没有说是10还是2）
把bit[i]，i从1到n都初始化为0。从第一个数开始过滤，每遇到一个数t都检查bit[t]是否是1。如果是1则找到，如果是0把bit[t]标记成1，直到找到一个标记成1的为止。这个算法显然时间和空间复杂度都是O(n)
我不是学算法的，只是想到一些理论上的思路，楼主要实际做的话肯定有很大优化余地。想法肯定不全面，说出来看看能不能帮到楼主。追问不是学算法的能想到这里就不错了……鄙人代表YCOI所有OIer感谢您提供方案，顺便一提，这东西叫哈希

热心网友 时间：2022-06-04 02:49

O（n）的算法是不可能存在的。即便是用哈希除非你能确保无冲突，不然也没在o（n）时间下完成。

热心网友 时间：2022-06-04 02:49

你的题目可能错了……应是：n是一个32位整数，n个数字的数组中，只有一个数字出现了1次，其余的数都出现了2次，且其余的数都不相等。求出现一次的数字。
Xor（异或）的性质，a xorb xor b=a xor(b xor b)=a xor 0=a;
知道这个性质可以这样：
Var n,I,x:,c,longint;
Begin
Readln(n);
Read(x);
For i:=2 to n do
begin
read(c)
X:=x xor c;
End;
Writeln(x);
End.