C++超时问题!! 程序运行结果正确,但是时间过长,请帮忙改进, 谢谢!! ;

2025-04-14 23:08:07
推荐回答(2个)
回答1:

你这个的复杂度是 n*n+2n了。
根据题目,因为数据时0~n-1,正好是数组下标,因此你只需
a[num[i]]=-2;
这样之后,所有存在的数都变成-2了,遍历a数组,找到不是-2的数,这时候a的下标就是结果了。这样做的程序复杂度是2N,应该就可以了。

回答2:

qsort一下num,然后挨个找,看看那两个数字被跳过了。。。
时间复杂度应该是 n log n