洛谷-P2249 【深基13.例1】查找

这个题目当我们看到单调不减.以及查找一个数字的时候就应该想到二分查找了.但是我们可以看到题目最后的说明,数据量是比较大的,并且也提示我们使用较快的IO方式.所以就不只是简单的二分查找,我们要通过一些手段来优化时间复杂度.

Python代码的话,我们可以先把待查询数组转成集合.一可以去重,二可以将查找的效率提高到O(1),我们先判断询问的数字在不在集合里面,不在的话就直接输出-1,否则的话再进行查询.代码如下:

import sys
from bisect import *

input = lambda: sys.stdin.readline().strip()
n, m = map(int, input().split())
lst = list(map(int, input().split()))
query = list(map(int, input().split()))
s = set(lst)
for i in query:
    if i not in s:
        print(-1, end=' ')
        continue
    index = bisect(lst, i - 1)
    print(index + 1, end=' ')

其中bisect是python一个非常常用的库,bisect函数原型为:bisect(a, x, lo=0, hi=None, *, key=None).其中a是我们要查询的数组,x是要查询的数字,lo代表起始索引,hi代表终止索引,并且查询区间是左闭右开区间.后面两个参数可以暂时不管,最后得到严格大于x的数字的索引.

C++代码的话,和Python是类似的,在algorithm库里有upper_bound函数和bisect效果是一样的,原型为ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );其中first就是起始迭代器,last就是终止迭代器,value就是我们要查找的值,并且采用和Python类似的手段,把数组转成集合来查询,提高效率,代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int>v(n);
    for (int i = 0; i < n; i++)cin >> v[i];
    unordered_set<int>us;
    us.reserve(v.size());
    us.insert(v.begin(), v.end());
    vector<int>q(m);
    for (int i = 0; i < m; i++)cin >> q[i];
    for (auto& num : q)
    {
        if (us.find(num) == us.end())
        {
            cout << -1 << " ";
            continue;
        }
        int index = upper_bound(v.begin(), v.end(), num - 1) - v.begin();
        cout << index + 1 << " ";
    }

}

洛谷-P2249 【深基13.例1】查找

洛谷-P2249 【深基13.例1】查找

评论交流