本文主要是介绍ACM程序设计课内实验（4）查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
补充知识
upper_bound()与lower_bound()使用方法
•都是二分函数，头文件<algorithm>
• upper_bound返回第一个大于的元素的下标；
• lower_bound返回第一个大于等于元素的下标；
1.二分查找
Description
有n(1<=n<=1000005)个整数，已经按照从小到大顺序排列好，现在另外给一个整数x，请找出序列中第1个大于x的数的下标！Input
输入数据包含多个测试实例，每组数据由两行组成，第一行是n和x，第二行是已经有序的n个整数的数列。Output
对于每个测试实例，请找出序列中第1个大于x的数的下标！。Sample Input
3 3 1 2 4Sample Output
2Hint
本题为多组数据，while(scanf("%d%d",&n,&m)!=-1)即可
库函数求解
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main() {int n, x;while (cin >> n >> x) {vector<int> nums(n);for (int i = 0; i < n; ++i) {cin >> nums[i];}int index = lower_bound(nums.begin(), nums.end(), x) - nums.begin();cout << index << endl;}return 0;
}
手写二分
#include <iostream>
#include <vector>using namespace std;int findFirstLargerIndex(const vector<int>& nums, int x) {int left = 0;int right = nums.size() - 1;int result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] > x) {result = mid;right = mid - 1;} else {left = mid + 1;}}return result ; // Adding 1 to get the 1-based index
}int main() {int n, x;while (cin >> n >> x) {vector<int> nums(n);for (int i = 0; i < n; ++i) {cin >> nums[i];}int result = findFirstLargerIndex(nums, x);cout << result << endl;}return 0;
}
2.查找出现次数
Description
给你n个int类型的数，让你统计出现次数最多的数字及次数？Input
输入1个N （1<=N<=20），数字值的范围【1，100】Output
输出出现次数最多的数字及次数Sample Input
8 2 2 2 2 3 3 56 7Sample Output
2 4
#include <iostream>
#include <unordered_map>
using namespace std;int main() {int n;cin >> n;int arr[n];for (int i = 0; i < n; i++) {cin >> arr[i];}unordered_map<int, int> count_map;for (int i = 0; i < n; i++) {count_map[arr[i]]++;}int max_count = 0;int max_num = 0;for (auto it = count_map.begin(); it != count_map.end(); it++) {if (it->second > max_count) {max_count = it->second;max_num = it->first;}}cout << max_num << " " << max_count << endl;return 0;
}
3.小清新的二分查找之旅
Description
小清新又在疯狂懵逼了，遇到了一道题，并且发誓绝对不会告诉别人：在题号899的题目上脸懵逼了好久，于是他决定强化一下题目900，以抒发心中的抑郁之气。所以…… 给出一组整数，整数个数为n，n不超过1,000,000，问这组整数中是否有k，总共询问q次。Input
多组输入。 每组输入输入： 第一行2个整数：n q ，1 <=q , n <= 1,000,000 。 第二行 有 n 个整数，已升序排序。所有数 <= 1 e 9+7. 第三行 有 q 个整数，用于查询。 每行各数据之间有空格隔开。Output
对每个查询数据分别输出一行 存在输出： no 不存在输出： YESSample Input
5 2 1 2 3 4 5 2 10Sample Output
no YES
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int n, q;while (cin >> n >> q) {vector<int> nums(n);for (int i = 0; i < n; ++i) {cin >> nums[i];}for (int i = 0; i < q; ++i) {int k;cin >> k;if (binary_search(nums.begin(), nums.end(), k)) {cout << "no" << endl;} else {cout << "YES" << endl;}}}return 0;
}
手写二分
#include <bits/stdc++.h>
using namespace std;
int n,q,k,i,l,r,m,a[1000010];
bool judge(int l,int r,int cmp)
{while(l<=r){m=l+(r-l)/2;if(a[m]>cmp) r=m-1;if(a[m]<cmp) l=m+1;if(a[m]==cmp) return 1;}return 0;
}
int main()
{ios::sync_with_stdio(false);while(cin>>n>>q){for(i=1;i<=n;i++)cin>>a[i];while(q--){cin>>k;if(judge(1,n,k))printf("no\n");else printf("YES\n");}}return 0;
}4.找自己
Description
给出一个无序数列a且数列a中无重复元素，给出该数列a中的某个元素x，求出该元素在该数列a的降序排列中所处的位置。Input
测试数据只有一组，第一行输入两个整数n，(1 <= n <= 500000)，m(0< m <= 10^9 )，n表示该数列a中元素的个数，m表示需要测试元素x的个数，第二行为n个整数，空格间隔，为数列a中的元素，接下来的m行，每行输入一个整数x，表示序列a中某个元素x。Output
对于每次输入的x，输出相应x在a的降序排列中所处的位置。每个输出占一行。Sample Input
6 3 3 1 4 5 9 2 9 5 2Sample Output
1 2 5
#include <vector>
#include <bits/stdc++.h>
using namespace std;int main() {int n, m;ios::sync_with_stdio(false);//加速时间scanf("%d %d", &n, &m);vector<int> a(n);for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}sort(a.begin(), a.end(), greater<int>());while (m--) {int x;scanf("%d", &x);auto it = lower_bound(a.begin(), a.end(), x, greater<int>());printf("%d\n", it - a.begin() + 1);}return 0;
}
5.找字符串
Description
程序完成在一些已知字符串中查找含有“*”最多的字符串的功能。要求用返回指针值的函数完成：找到这个字符串，函数返回“*”最多的字符串的首地址，若所有字符串中均不含“*”，则返回NULL。并将找到的字符串输出。 要求：用返回指针值的函数完成查找，在main中将其输出。Input
put ：输入数据有多组，每组包括两行，第一行1个整数n，表示n个各不相同的字符串（n<=100）；第二行是n个长度不超过50的字符串，每个之间用空格分隔。Output
将找到的字符串输出。每个一样输出。Sample Input
4abc*kie** *kdiei*kdi*ki** i*9k*kiei* iie 5 abc iie*ki* kie***** *kidi* 909*Sample Output
*kdiei*kdi*ki** kie*****
#include <stdio.h>
#include <stdlib.h>int len(char *p) {int i = 0, ans = 0;while (p[i] != '\0') {if (p[i] == '*') ans++;i++;}return ans;
}char *js(char *p[101], int n) {int i, num = 0, k = 1;for (i = 1; i <= n; i++) {int tp = len(p[i]);if (num < tp) {num = tp;k = i;}}return p[k];
}int main() {char a[101][51];char *p[101];int n, i;while (scanf("%d", &n) != -1) {for (i = 1; i <= n; i++) {p[i] = (char *)malloc(51 * sizeof(char));scanf("%s", p[i]);}char *ans = js(p, n);printf("%s\n", ans);}return 0;
}
这篇关于ACM程序设计课内实验（4）查找的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
