使用二分查找或者map进行快速查找

查找

http://www.nowcoder.com/questionTerminal/d93db01c2ee44e8a9237d63842aca8aa

使用map时间复杂度为O(m)

#include <iostream>
#include <map>
using namespace std;

int main() {
    int n;
    int m;
    while(cin>>n) {
        map<int,bool> mp;
        for (int i = 0; i < n; i++) {
            int temp;
            cin>>temp;
            mp[temp] = true;
        }
        cin>>m;
        for (int i = 0; i < m; i++) {
            int temp;
            cin>>temp;
            if (mp.find(temp) != mp.end()) {
                cout<<"YES"<<endl;
            } else {
                cout<<"NO"<<endl;
            }
        }
    }
}

使用二分查找时间复杂度为O(mlogn)

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

int main() {
    int n;
    int m;
    while(cin>>n) {
        int *arr = new int[n];
        for (int i = 0; i < n; i++) {
            cin>>arr[i];
        }
        sort(arr, arr+n);
        cin>>m;
        int *test = new int[m];
        for (int i = 0; i < m; i++) {
            cin>>test[i];
            if (binary_search(arr, arr + n, test[i])) {
                cout<<"YES"<<endl;
            } else {
                cout<<"NO"<<endl;
            }
        }
    }
}
全部评论

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
MinJerous:虽然我一直说 计算机不怎么卡学历 但是至少得一本
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 11:30
仁者伍敌:kpi都懒得刷了属于是
点赞 评论 收藏
分享
评论
4
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务