回 帖 发 新 帖 刷新版面

主题:[讨论]在有序整数组中用O(n)算法求是否有两数和为X,谁有较好的思想的?

令A[1..n]是一个n个整数和已排序的数组,x是整数。请设计一个O(n)时间的算法来确定在A中是否存在这样的两个数,它们的和恰好是X。

还有,如果要求证是否存在这样的三个数它们的和恰好是X的算法。

谁对这两个问题有较好的思想的,可以说一说不?

对于验证两个数的,我的想法是这样的:
bool FindX::get2Result(int *data,int size, int x, int *r1, int *r2)
{
    int i,j,n;
    for(j=size-1;j>=0;j--)
    {
        if(data[j]<x)
            break;
    }
    n=j;
    i=0;
    while(i<=n&&j>=0)
    {
        if(data[i]+data[j]>x)
        {
            j--;
        }
        else if(data[i]+data[j]<x)
        {
            i++;
        }
        else
        {
            *r1=i;
            *r2=j;
            return true;
        }
    }
    return false;
}
但没有证明过这样是否正确,望有高人指点一下,any answer will be appreciated~~[em1]

回复列表 (共3个回复)

沙发


都一个星期了。。没人帮忙吗??

板凳

楼主的方法是可行的,可以用反证法证明

3 楼

实现的时候bool FindX::get2Result(int *data,int size, int x, int *r1, int *r2)要改下吧。
r1和r2用引用可以。
#include <iostream>
using namespace std;

bool get2Result(int *data,int size, int x, int &r1, int &r2)
{
    int i,j,n;
    for(j=size-1;j>=0;j--)
    {
        if(data[j]<x)
            break;
    }
    n=j;
    i=0;
    while(i<=n&&j>=0)
    {
        if(data[i]+data[j]>x)
        {
            j--;
        }
        else if(data[i]+data[j]<x)
        {
            i++;
        }
        else
        {
            r1=i;
            r2=j;
            cout<<r1<<endl;
            cout<<r2<<endl;
            return true;
        }
    }
    
    return false;
}
int main()
{
    const int size=6;
    int data[size]={1,2,5,8,6,9};
    int x=8,r1,r2;
    bool r=get2Result(data,size,x,r1,r2);
    cout<<r<<endl;
    return 0;
}

我来回复

您尚未登录,请登录后再回复。点此登录或注册