给定n个整数的数组并给出数字X,找到所有唯一的元素对(a,b),其总和等于X.
以下是我的解决方案,它是O(nLog(n)+ n),但我不确定它是否是最优的.
int main(void)
{
int arr [10] = {1,2,3,4,5,6,7,8,9,0};
findpair(arr, 10, 7);
}
void findpair(int arr[], int len, int sum)
{
std::sort(arr, arr+len);
int i = 0;
int j = len -1;
while( i < j){
while((arr[i] + arr[j]) <= sum && i < j)
{
if((arr[i] + arr[j]) == sum)
cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
i++;
}
j--;
while((arr[i] + arr[j]) >= sum && i < j)
{
if((arr[i] …我们需要在数组中找到一对数,其总和等于给定值.
A = {6,4,5,7,9,1,2}
Sum = 10然后对是 - {6,4},{9,1}
我有两个解决方案.
sum-hash[i]哈希表中是否存在.但是,问题在于虽然第二种解决方案是O(n)时间,但也使用O(n)空间.
所以,我想知道我们是否可以在O(n)时间和O(1)空间中完成它.这不是功课!
摘自算法简介
描述一个Θ(n lg n)时间算法,给定一组n个整数和另一个整数x,确定S中是否存在两个元素,其和是x.
到目前为止,这是我用Java实现的最佳解决方案:
public static boolean test(int[] a, int val) {
mergeSort(a);
for (int i = 0; i < a.length - 1; ++i) {
int diff = (val >= a[i]) ? val - a[i] : a[i] - val;
if (Arrays.binarySearch(a, i, a.length, diff) >= 0) {
return true;
}
}
return false;
}
现在我的第一个问题是:这是一个正确的解决方案吗？根据我的理解,mergeSort应该在O(n lg n)中执行排序,循环应该取O(n lg n)(n用于迭代乘以O(lg n)进行二进制搜索,得到O(2 l lg) n),所以它应该是正确的.
我的第二个问题是:有更好的解决方案吗？排序阵列必不可少？
问题:给定一个未排序的正整数数组,是否有可能从该数组中找到一对总和达到给定总和的整数？
约束:这应该在O(n)和就地(没有任何外部存储,如数组,哈希映射)完成(你可以使用额外的变量/指针)
如果这是不可能的,那么可以给出相同的证明吗？
设计一种算法来查找数组中总和为指定值的所有整数对.
我已经尝试使用哈希表来存储数组元素总和的条目,但它不是一个有效的解决方案.
我可以使用什么算法来有效地解决这个问题？
可能重复:
给定两个数组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++数据结构,即空间没有界限
给定一个非常大的整数数组,我需要找到最大值a4,这样:
a4 = a1 + a2 + a3
其中ai是数组中的所有值.
我该怎么做？
注意:使用4 for循环不是理想的解决方案.
我看到一个面试问题如下:给出一个未排序的整数数组A和一个整数I,找出A的任何两个成员是否加起来我.
任何线索？
时间复杂度应该更少