今天的题目也不难，算是接触一下基本的算法思路，二分就过了，但是，我们就这么屈服了？？？那不能。我们要整活。多种解法的冲！！！！！
4.2日每日一题——查找
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min
全文目录
☘前言☘
解题思路一
解题思路二
解题思路三
📑写在最后
P2249 【深基13.例1】查找
解题思路一
暴力，直接写，直接冲。
#include <stdio.h> #include <stdlib.h> int data[1000005]; int main(){ int m,n,x; scanf("%d %d",&m,&n); for(int i = 0;i < m;++i) scanf("%d",&data[i]); for(int i = 0;i < n;++i){ scanf("%d",&x); int j; for(j = 0; j < m;++j) if(data[j] < x) continue; else break; if(j < m && data[j] == x) printf("%d ",j+1); else printf("-1 "); } return 0; }
炸咯！！！！！！！！！！！！！！！！！！！！！！！
解题思路二
二分是不可能二分的，我就不二分。一次性读入所有待查询的数据，然后将待查询的数据排序，之后从前往后扫就行了，时间复杂度就是 l o g ( m ) + n + l o g ( m ) log(m) + n + log(m)log(m)+n+log(m)，本质上就是减少了指针的回溯。
#include <stdio.h> #include <stdlib.h> int data[1000005]; typedef struct{ int id,data,ans; }Search; Search search[100005]; int cmpdata(const void * a, const void *b){ return ((Search *)a)->data < ((Search *)b)->data ? -1 : 1; } int cmpid(const void * a, const void *b){ return ((Search *)a)->id < ((Search *)b)->id ? -1 : 1; } int main(){ int m,n; scanf("%d %d",&m,&n); for(int i = 0;i < m;++i) scanf("%d",&data[i]); for(int i = 0;i < n;i++) {scanf("%d",&search[i].data);search[i].id = i;} qsort(search, n, sizeof(Search), cmpdata); for(int i = 0,j =0 ;j < n;++j){ while(i < m && data[i] < search[j].data) ++i; if(i < m && data[i] == search[j].data) search[j].ans = i+1; else search[j].ans = -1; } qsort(search, n ,sizeof(Search),cmpid); for(int i = 0;i < n;++i) printf("%d ", search[i].ans); return 0; }
Ohhhhhhhhhhhhhhhhhh~~~~~~~~~过啦
解题思路三
读一个查一个，但是查找的过程使用二分查找。
#include <stdio.h> #include <stdlib.h> int data[1000005]; int search(int x, int l, int r){ while(l < r){ int mid = l + (r -l)/2; if(data[mid] >= x) r = mid; else l = mid + 1; } if(data[l] == x) return l + 1; return -1; } int main(){ int m,n,x; scanf("%d %d",&m,&n); for(int i = 0;i < m;++i) scanf("%d",&data[i]); for(int i = 0;i < n;++i){ scanf("%d",&x); printf("%d ",search(x,0,m - 1)); } return 0; }
OHhhhhhhhhh~~也过啦
📑写在最后
其实我也尝试了将后两种方式融合一下，但是效果并不好，大家可以多思考一些解决方法，其实很多时候如果查询数据量高于数据量本身。可能方法二就会更好。大家一起加油呀0.0
其实我第二种解法错了十几次，原因是忘了本身的次序，哎，还是太菜了，要好好学习呀
