5. 简单查找问题

题目来源和说明

题目是2010年哈尔滨工业大学计算机研究生机试真题，像通过本次例题梳理和掌握简单的查找算法，后续可能会更一期其他难度更大的查找算法

题目描述

输入一个数n，然后输入n个数值各不相同，再输入一个值x，输出这个值在这个数组中的下标（从0开始，若不在数组中则输出-1）

样例

输入：
2
1 3
0
输出：
-1

简要分析

水题不解释啦，看代码吧，相信都能看懂~

C++ 代码

#include<iostream>
using namespace std;

int buf[200];
int main() {
	int n;
	while(scanf("%d",&n)!=EOF) {
		for(int i=0;i<n;i++) {
			scanf("%d",&buf[i]);	
		}
		int x,ans=-1;
		scanf("%d",&x);
		for(int i=0;i<n;i++) {
			if(x==buf[i]) {
				ans=i;
				break;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

简要分析

看到这个题，可能回想这和第一个水题有什么区别呢？我只要重复查找几次不就好了，多个for循环而已。但是需要注意的任何一个题目解决前都需要考虑事件复杂度。按照上面说的每次询问都线性遍历数组来查找是否存在我们需要查找的元素，那么该算法的时间复杂度最坏可以达到O（n*m），而这已经达到了千万数量级，是我们不愿意看到的。于是，我们只能另找方法来解决该题。没错，就是二分查找。为了符合查找空间单调有序的要求，我们首先要对所有数组元素按照学号关键字升序排列（时间复杂度是O（nlgn）。当数组内个元素已经升序有序时，我们就可以在每次询问某个特定学号的学生是否存在时，使用二分查找来查找该学生（时间辐照度是O（mlgn）.综上时间复杂度已经降至百万级别，属于可行方案。下面是代码：

C++代码

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

struct Stu{
    char no[100];
    char name[100];
    int age;
    char sex[5];
    bool operator<(const Stu& A) const {//重载小于运算符使其能够使用sort函数排序
        return strcmp(no,A.no)<0;
    }
}buf[1000];

int main() {
    int n;
    while(scanf("%d",&n)!=EOF) {
        for(int i=0;i<n;i++) {
            scanf("%s%s%s%d",buf[i].no,buf[i].name,buf[i].sex,&buf[i].age);
        }
        sort(buf,buf+n); //对数组排序，使其按照学号升序排列
        int t;
        scanf("%d",&t); //有t组询问
        while(t--!=0) { //while循环保证查询次数为t
            int ans=-1; 
            char x[30];
            scanf("%s",x); //待查找学号
            int r=n-1,l=0;
            while(l<=r) { //当查找子集不为空集时重复二分查找
                int mid=l+(r-l)/2;
                int temp=strcmp(buf[mid].no,x);
                if(temp==0) {
                    ans=mid;
                    break;
                }
                else if(temp>0) r=mid-1;
                else l=mid+1;
            }
            if(ans==-1) { //没找到
                printf("No Answer!\n");
            }
            else printf("%s %s %s %d\n",buf[ans].no,buf[ans].name,buf[ans].sex,buf[ans].age);
        }
    }
    return 0;
}

打印极值点下标

https://www.nowcoder.com/questionTerminal/7fd72f8ac7964ba3b8baa8735246e1f1

简要分析

这个题数据量比较小，直接线性查找，寻找极值点就行，极值点的判定条件是：(a[i-1]<a[i]&&a[i]>a[i+1])||(a[i-1]>a[i]&&a[i]<a[i+1])，但是直接注意的是需要对第一个和最后一个进行特判。注意到这点应该就没啥坑了~

C++代码

#include<iostream>
using namespace std;
int a[85];
int b[85];
int main() {
    int n;
    while(scanf("%d",&n)!=EOF) {
        int cnt=0;
        for(int i=0;i<n;i++) {
            scanf("%d",&a[i]);
        }
        if(a[0]<a[1] || a[0]>a[1]) b[cnt++]=0;
        for(int i=1;i<n-1;i++) {
            if((a[i-1]<a[i]&&a[i]>a[i+1])||(a[i-1]>a[i]&&a[i]<a[i+1])) {
                b[cnt++]=i;
            }
        }
        if(a[n-1]<a[n-2] || a[n-1]>a[n-2]) b[cnt++]=n-1;
        for(int i=0;i<cnt;i++) {
            if(i==cnt-1) printf("%d\n",b[cnt-1]);
            else printf("%d ",b[i]);
        }
    }
    return 0;
}

5. 简单查找问题

题目来源和说明

题目描述

样例

简要分析

C++ 代码

同类题目

简要分析

C++代码

简要分析

C++代码