即使在数组上执行了上限,也超过了时间限制

使用的语言:C ++ 14。

给我2个排序数组A和B。现在,对于A中的每个元素,如果可能的话,我必须在B中找到一个更大的元素。我正在做这样的事情:

int j=0;
for(i=0;i < A.size();i++)
{
    int index = upper_bound(B.begin()+j,B.end(),A[i]) - B.begin();
    if(index>=B.size()){
        break;
    }
    else{
        cout<<"For A[]"<<A[i]<<" element "<<B[index]<<" is greater "<<"\n";
        j = index + 1;
    }
}

即使我正在使用upper_bound进行二进制搜索时,程序仍然给出了超出大型数组(例如大小为1000000)的时间限制。

我不知道为什么?

附言:我知道这可以在线性时间内使用2个指针来完成,但是我想知道为什么我的解决方案失败了。我是新来者,请帮帮我。

评论
  • 猪猪侠
    猪猪侠 回复

    首先,请确保upper_bound中的第一个迭代器<=第二个迭代器,因为对于某些数字,数组B中的最后一个元素可能大于它,所以现在如果执行j = index + 1,则它将等于B.end(),现在搜索更大的元素将总是返回比B的长度大的整数,这是不可能的。

    其次,您的问题是:

    int index = upper_bound(B.begin()+j,B.end(),A[i]) - B.begin();
    

    This line is moving the first iterator by 'j' steps first and not in constant time and then applying upper_bound would result in a time complexity of o(n*n*log(n))

    n:用于遍历A

    n:以“ j”步移动,在最坏的情况下可以为n

    log(n):对于upper_bound

    这导致较大阵列的时间限制。