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

Question

使用的语言：C++14。

我得到了 2 个排序数组 A 和 B。现在，对于 A 中的每个元素，如果可能的话，我必须在 B 中找到一个更大的元素，并注意一旦我在 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 ).

我想不通为什么？

P.S：我知道这可以在线性时间内使用 2 个指针来完成，但是我想知道为什么我的解决方案失败了。我是新来的，所以请帮助我。

Answer 1

首先确保 upper_bound 中的第一个迭代器 <= 第二个迭代器，因为对于某些数字，数组 B 中的最后一个元素可能会大于它，所以现在如果你这样做j = index + 1，它将等于 B.end()，现在搜索任何更大的元素总是 return 某个大于 B 长度的整数，这是不可能的。

其次，对于你的问题：

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

此行首先将第一个迭代器移动 'j' 步 并且 不是恒定时间 然后应用 upper_bound 会导致时间复杂度为 o(n*n*log(n))

n：用于遍历 A

n：移动 'j' 步，在最坏的情况下可以是 n

log(n) : 对于 upper_bound

导致较大数组的时间限制。

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

Time limit exceeded even after doing an upper_bound on the array

c++

sorting

stl

binary-search