查找类问题
标签: 机试攻略 - 高分篇
学习人数: 34.9k


高清播放
赞赏支持

查找是一类我们必须掌握的算法,它不仅会在题目中直接考察,同时也可能是其他算法中的重要组成部分。本章中介绍的查找类问题都是单独的基础查找问题,对于这类基础查找的问题,我们应该将它完全掌握。

 

查找类题目一般有以下几种考点

1、数字查找:给你一堆数字,让你在其中查找x是否存在
题目变形:如果x存在,请输出有几个。
2、字符串查找:给你很多个字符串,让你在其中查找字符串s是否存在

顺序查找就不说了,这个大家会。

 

什么时候不能用顺序查找呢?
很明显,当满足下面这种情况的时候

1、数据量特别大的时候,比如有10W个元素。
2、查询次数很多的时候,比如要查询10W次。

 

遇到这类题大多数人的想法是先sort排序,然后二分查找,这是一个很常规的解决这类问题的方法。
但是,我们不推荐你这么做,我们有更简单易用且快速的方法。我们推荐你了解并使用map容器。

 

前面介绍过map,它是STL的一种关联式容器,它的底层是红黑树实现的,也就意味着它的插入和查找操作都是log级别的。
相信每一个用过map的同学,都会情不自禁的说一句,map真香!

 

查找学生信息2
题目描述:
输入N个学生的信息,然后进行查询。
输入描述:
输入的第一行为N,即学生的个数(N<=1000)
接下来的N行包括N个学生的信息,信息格式如下:
01 李江 男 21
02 刘唐 男 23
03 张军 男 19
04 王娜 女 19
然后输入一个M(M<=10000),接下来会有M行,代表M次查询,每行输入一个学号,格式如下:
02
03
01
04
输出描述:
输出M行,每行包括一个对应于查询的学生的信息。
如果没有对应的学生信息,则输出“No Answer!”
输入样例#:
4
01 李江 男 21
02 刘唐 男 23
03 张军 男 19
04 王娜 女 19
5
02
03
01
04
03
输出样例#:
02 刘唐 男 23
03 张军 男 19
01 李江 男 21
04 王娜 女 19
03 张军 男 19
题目来源:
DreamJudge 1476

题目解析:对于这类查询量大的题目,我们有两种方法来解决这个问题。第一是将学号先排好序,然后使用二分查找,但是很多同学写二分的时候容易出现问题,而且代码量也比较大,我们不推荐这种做法。推荐大家使用map来解决这类问题,基本上map可以通过99.9%的这类题目。

 

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
struct node{  
    string num;  
    string name;  
    string sex;  
    int age;  
};  
int main(){  
    int n,q;  
    map<string, node> M;//定义一个map映射  
    while(scanf("%d", &n)!=EOF){  
        for(int i=0;i<n;i++){  
            node ...
登录查看完整内容


课后作业

练习题目

DreamJudge 1177 查找学生信息
DreamJudge 1388 查找1
DreamJudge 1387 查找 - 北邮
DreamJudge 1383 查找第K小数


登录后开始许愿

1 条上岸许愿
星月争辉
2024年3月14日 23:00

dd

赞(0)