ACM程序设计课内实验（4）查找

拼搏现实的明天。 2024-04-17 13:41 68阅读 0赞

## 补充知识 ##

> upper\_bound()与lower\_bound()使用方法
> 
> •都是二分函数，头文件<algorithm>
> 
> • upper\_bound返回第一个大于的元素的下标；
> 
> • lower\_bound返回第一个大于等于元素的下标；

## 1.[二分查找][Link 1] ##

> #### Description ####
> 
>     有n(1<=n<=1000005)个整数，已经按照从小到大顺序排列好，现在另外给一个整数x，请找出序列中第1个大于x的数的下标！
> 
> #### Input ####
> 
>     输入数据包含多个测试实例，每组数据由两行组成，第一行是n和x，第二行是已经有序的n个整数的数列。
> 
> #### Output ####
> 
>     对于每个测试实例，请找出序列中第1个大于x的数的下标！。
> 
> #### Sample Input ####
> 
>     3 3
>     1 2 4
> 
> #### Sample Output ####
> 
>     2
> 
> #### Hint ####
> 
>     本题为多组数据，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.[查找出现次数][Link 2] ##

> #### Description ####
> 
>     给你n个int类型的数，让你统计出现次数最多的数字及次数？
> 
> #### Input ####
> 
>     输入1个N （1<=N<=20），数字值的范围【1，100】
> 
> #### Output ####
> 
>     输出出现次数最多的数字及次数
> 
> #### Sample Input ####
> 
>     8
>     2 2 2 2 3 3 56 7
> 
> #### Sample 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.[小清新的二分查找之旅][Link 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
>     不存在输出：
>     YES
> 
> #### Sample Input ####
> 
>     5 2
>     1 2 3 4 5
>     2 10
> 
> #### Sample 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.[找自己][Link 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
>     2
> 
> #### Sample 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.找字符串][5.] ##

> #### Description ####
> 
>     程序完成在一些已知字符串中查找含有“*”最多的字符串的功能。要求用返回指针值的函数完成：找到这个字符串，函数返回“*”最多的字符串的首地址，若所有字符串中均不含“*”，则返回NULL。并将找到的字符串输出。
>     要求：用返回指针值的函数完成查找，在main中将其输出。
> 
> #### Input ####
> 
>     put ：
>        输入数据有多组，每组包括两行，第一行1个整数n，表示n个各不相同的字符串（n<=100）；第二行是n个长度不超过50的字符串，每个之间用空格分隔。
> 
> #### Output ####
> 
>     将找到的字符串输出。每个一样输出。
> 
> #### Sample Input ####
> 
>     4
>      abc*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;
    }

[Link 1]: https://acm.webvpn.nefu.edu.cn/problemShow.php?problem_id=956
[Link 2]: https://acm.webvpn.nefu.edu.cn/problemShow.php?problem_id=2359
[Link 3]: https://acm.webvpn.nefu.edu.cn/problemShow.php?problem_id=1646
[Link 4]: https://acm.webvpn.nefu.edu.cn/problemShow.php?problem_id=611
[5.]: https://acm.webvpn.nefu.edu.cn/problemShow.php?problem_id=1025