我有一个整数数组,我需要一个O(n)算法来查找数组是否包含数字及其平方; 一对就足够了.
我试图自己做,但我只是设法找到O(n 2)的解决方案.
我想过使用计数排序,但内存使用量太大了.
Chr*_*s H 12
创建一个两倍于输入数组长度的新数组.O(2N)
复制O(N)中的所有数字
复制O(N)
基数排序中的数字的平方(我们可以因为它们都是整数)O(N)
迭代一次以查看是否有两个数字另一个O(N)
利润之后的同一个!O(1)
| 归档时间： |
|
| 查看次数： |
3549 次 |
| 最近记录： |