时间戳

首页 > 解决方案 > 涉及上限和下限的问题

c++ - 涉及上限和下限的问题

问题描述

在排序数组中查找给定数字的最后一次和第一次出现的位置。如果数字不存在，则将下限和上限打印为 -1。我编写了如下代码，但我无法通过所有测试用例。谁能告诉我为什么？

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    vector<int> v;
    int n,num,q,find;
    cin>>n;
    v.reserve(n);

    for(int i=0;i<n;i++){
        cin>>num;
        v.push_back(num);
    }
    sort(v.begin(),v.end());
    cin>>q;

    while(q--){
        cin>>find;
        auto lb=lower_bound(v.begin(),v.end(),find);
        auto ub=upper_bound(v.begin(),v.end(),find);

        if(lb==v.end() || v.empty()){
            cout<<-1<<" "<<-1<<endl;
        }

        else{
            cout<<lb-v.begin()<<" "<<ub-v.begin()-1<<endl;
        }
    }

    return 0;
}

标签： c++

解决方案

std::lower_bound(first, last, value)没有找到等于 的元素value，它找到了下界（不小于 的第一个元素value），顾名思义。例如，对于范围1 3 5和目标值2，它将返回指向的迭代器3。

要检查元素是否存在于数组中，您可以编写

auto pos = std::lower_bound(first, last, value);
if (pos != last && *pos == value)
    // ...

还应该注意的是，两次调用std::lower_bound和std::upper_bound可以替换为一次调用std::equal_range。

推荐阅读