Deb*_*nda 9 c++ arrays algorithm
可能重复:
给定两个数组a和b.查找所有元素对(a1,b1),使得a1属于数组A,b1属于数组B,其总和a1 + b1 = k.
给定:未排序A的整数数组
输入:整数k
输出:所有两个元素集合,每个元素的总和等于kO(n).
例:
A = {3,4,5,1,4,2}
输入:6
输出:{3,3}, {5,1}, {4,2}
注意:我知道一个O(n logn)解决方案,但这需要对数组进行排序.有没有办法在O(n)中解决这个问题.可以使用非平凡的C++数据结构,即空间没有界限
小智 18
创建一个恒定时间查找表(哈希),以便查看数组中是否包含特定的整数(O(n)).然后,对于数组中的每个元素,请查看是否k-A[i]包含.这需要每个元素保持恒定的时间,因此总共有O(n)时间.这假设元素是不同的; 使重复元素工作并不困难.
| 归档时间： |
|
| 查看次数： |
13642 次 |
| 最近记录： |