查找__牛客网

小陈也只是想要一个实习罢了

//先记一个别的做法，这个空间换时间做的还是不错的，o(m)的时间，就是这个范围有点难确定
#include<bits/stdc++.h>
int main(){
    int m,n,s;
    while(scanf("%d",&n)!=EOF){
        int a[1000]={0};
        for(int i=0;i<n;i++){
            scanf("%d",&m);
            a[m]=1;
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d",&s);
            if(a[s]==1) printf("YES\n");
            else printf("NO\n");
        }
    }
}//hash法
//下面这个自己写的时间复杂度是o(m*n)因为感觉说了m,n的范围都在100以内，所以即使乘积也不会超限
#include<iostream>
using namespace std;
int main(){
    int n,m;
    while(cin>>n){
        int *a=new int[n],b;
        for(int i=0;i<n;i++)
            cin>>a[i];
        cin>>m;
        for(int i=0;i<m;i++){
            cin>>b;
            bool judge=1;
            for(int j=0;j<n&&judge;j++)
                if(b==a[j]){
                    cout<<"YES"<<endl;
                    judge=0;
                }
            if(judge)
                cout<<"NO"<<endl;
        }
    }
    return 0;
}

发表于 2020-01-14 15:29:12 回复(2)

C/C++

Medivh!

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int x[102];
    int n, q, m;
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> x[i];
        }
        sort(x, x+n);
        cin >> m;
        while (m--) {
            cin >> q;
            cout << ((*lower_bound(x, x+n, q) == q) ? "YES" : "NO") << endl;
        }
    }
}

发表于 2018-03-15 11:24:09 回复(0)

C/C++

My_C

#include <iostream>
using namespace std;
int main(){
    int n,m;
    while(cin>>n){
        int i,a[100],b[100];
        for(i=0;i<n;i++)
            cin>>a[i];
        cin>>m;
        for(i=0;i<m;i++)
            cin>>b[i];
        for(i=0;i<m;i++){
            bool flag=false;
            for(int j=0;j<n;j++){
                if(b[i]==a[j]){
                    flag=true;
                    break;
                }
            }
            if(flag) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
    return 0;
}

发表于 2017-12-13 17:57:44 回复(0)

啥也不是1024

#include <bits/stdc++.h>
using namespace std;
int x,n,m,num[100];	
map<int,int> M;
int main()
{
    cin>>n;   
	for(int i =0;i<n;i++)
	{
        cin>>x;
		M[x]++;
	}
    cin>>m;
    for(int i=0;i<m;i++)
        cin>>num[i];
    for(int i =0;i<m;i++)
    {
        if(M[num[i]]==0)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
	return 0;
}

利用Map查找

发表于 2020-03-04 12:47:50 回复(0)

C/C++

握着我的抱枕

tips：3个数组，用2个数组储存输入，2个循环比较，用第3个数组储存结果进行输出

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n, m;
	int a[100] ={0};
	int b[100] ={0};
	int c[100] ={0};
	while (cin >> n) {
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		cin >> m;
		for (int i = 0; i < m; i++) {
			cin >> b[i];
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (b[i] == a[j]) {
					c[i] = 1;
					break;
				}
			}
		}
		for (int i = 0; i < m; i++) {
            if (c[i] == 1)
                cout << "YES"<<endl;
            if(c[i]==0)
                cout << "NO"<<endl;;
		}
	}
	return 0;
}

发表于 2020-02-19 00:20:06 回复(0)

发愤图强的小菜

时间复杂度O(n)

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        while (in.hasNext()){
            int n=in.nextInt();
            Set<Integer> set=new HashSet<Integer>();

            for (int i=0;i<n;i++)
                set.add(in.nextInt());

            n=in.nextInt();
            for (int i=0;i<n;i++){
                int a=in.nextInt();
                if (set.add(a))
                {
                    set.remove(a);
                    System.out.println("NO");
                }

                else
                    System.out.println("YES");
            }

        }
    }
}

发表于 2017-05-26 14:59:19 回复(0)

C/C++

KDDA十三尧十三

#include<iostream>
#include<vector>
using namespace std;

int main(void)
{
    int n;
    vector<int> a;
    vector<int> b;
    
    while(cin >> n)
    {
        for(int i = 0;i < n;i++)
        {
            int x;
            cin >> x;
            a.push_back(x);
        }
        
        int m;
        cin >> m;
        for(int i = 0;i < m;i++)
        {
            int y;
            cin >> y;
            b.push_back(y);
        }
        
        for(int i = 0;i < m;i++)
        {
            int count = 0;//标记是否有相同数字的个数
            for(int j = 0;j < n;j++)
            {
                if(b[i] == a[j])
                    count++;
            }
            if(count == 0)
                cout << "NO" << endl;
            else
                cout << "YES" << endl;
        }
    }
    return 0;
}

发表于 2021-02-22 16:19:52 回复(0)

C/C++

想了三天不知道叫什么

#include<stdio.h>
#include<stdlib.h>

//比较函数
int cmp_inc(const void* a,const void* b){
    return *(int *)a - *(int *)b;
}

//二分查找
int Binary_Search(int *arr,int n,int key){
    int low=0;
    int high=n-1;
    int mid;
    while(low<=high){
        mid=(low+high)/2;
        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]<key){
            low=mid+1;
        }
        else{
            high=mid-1;
        }
    }
    return -1;
}

int main(){
    int n,m;
    int a[100];
    int b[100];
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        qsort(a,n,sizeof(int),cmp_inc);
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d",&b[i]);
        }
        for(int i=0;i<m;i++){
            int s=Binary_Search(a,n,b[i]);
            if(s!=-1){
                printf("YES\n");
            }else{
                printf("NO\n");
            }
        }
    }
}

编辑于 2021-01-31 11:44:47 回复(0)

mrvoider

#include <bits/stdc++.h>

using namespace std;

int a[101],b[101];
bool flag[101];

int main()
{
    int n,m;
    int i;
    scanf("%d",&n);
    for(i = 0; i < n; i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a, a+n);
    scanf("%d",&m);
    for(i = 0; i < m; i++)
    {
        scanf("%d",&b[i]);
        flag[i] = binary_search(a, a+n, b[i]);
    }
    for(i = 0; i < m;i++)
    {
        if(flag[i]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    
    return 0;
}

好像用STL好像没什么意思，反正思路是这样的。。

发表于 2021-01-27 21:24:48 回复(0)

道纪书生

#include<bits/stdc++.h> //万能头
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;

int BinarySearch(int a[],int n,int b)
{
	int left=0;
	int right=n-1;
	while(left<=right)
	{
		int middle=(left+right)/2;
		if(a[middle]<b)
		{
			left=middle+1;
		}
		else if(b<a[middle])
		{
			right=middle-1;
		}
		else
		{
			return 1;
		}
	}
	return 0;
	
}

int main(){
	int m,n;
	while(scanf("%d",&n)!=EOF)
	{
		int a[n];
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
		scanf("%d",&m);
		sort(a,a+n);
		int b[m];
		for(int i=0;i<m;i++)
		{
			scanf("%d",&b[i]);
		}
		for(int i=0;i<m;i++)
		{
			if(BinarySearch(a,n,b[i] )==1)
			{
				printf("YES\n");
			}
			else
			{
				printf("NO\n");
			}
		}
		
		
	} 
    return 0;
}

发表于 2020-09-10 10:45:24 回复(0)

Java

LHC0512

Java解法

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) set.add(scanner.nextInt());
        int m = scanner.nextInt();
        for (int i = 0; i < m; i++) System.out.println(set.contains(scanner.nextInt())?"YES":"NO");
    }
}

发表于 2020-03-14 16:29:34 回复(0)

C/C++

Orin

#include <stdio.h>
#include <algorithm>
using namespace std;

int main()
{
    int n,m;
    int buf[100];
    int top,base,mid;
    int ans=-1;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++)
            scanf("%d",&buf[i]);
        sort(buf,buf+n);
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            ans=-1;
            int tmp;
            scanf("%d",&tmp);
            top=n-1;
            base=0;
            mid=(top+base)/2;
            while(base<=top){
                if(buf[mid]==tmp){
                    ans=1;
                    break;
                }
                else{
                    (buf[mid]>tmp)?(top=mid-1):(base=mid+1);
                    mid=(top+base)/2;
                }
            }
            if(ans==-1)    printf("NO\n");
            else    printf("YES\n");
        }
    }
    return 0;
}

发表于 2019-04-30 11:48:51 回复(0)

hushhw

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <set>
using namespace std;

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int num;
        set<int> a;
        for (int i = 0; i<n; i++){
            scanf("%d", &num);
            a.insert(num);
        }
        int m,c;
        scanf("%d", &m);
        for (int i = 0; i < m; i++){
            scanf("%d", &c);
            if(a.find(c)!=a.end()){
                printf("YES\n");
            }else{
                printf("NO\n");
            }
        }
    }
    return 0;
}

发表于 2019-03-01 19:36:06 回复(0)

sunlanchang

二分查找STL中bug-free实现

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1111;
int num[maxn];
int low_bound(int first, int last, int value)
{
    while (first < last)
    {
        int mid = first + (last - first) / 2; // 防溢出
        if (value > num[mid])
            first = mid + 1;
        else
            last = mid;
    }
    return first;
}
int main()
{
    // freopen("in.txt", "r", stdin);
    int n, m;
    while (~scanf("%d", &n))
    {
        for (int i = 0; i < n; i++)
            scanf("%d", &num[i]);
        sort(num, num + n);
        scanf("%d", &m);
        for (int i = 0; i < m; i++)
        {
            int value;
            scanf("%d", &value);
            int index = low_bound(0, n, value);
            if (value == num[index])
                puts("YES");
            else
                puts("NO");
        }
    }
    return 0;
}

编辑于 2019-01-31 19:05:47 回复(0)

明达超级幸运(ง•_•)ง

#include<stdio.h>
#include<algorithm>
using namespace std;
int solve(int a[],int left,int right,int k){
    int mid;
    while(left<right){
        mid=(left+right)/2;
        if(k<=a[mid])
            right=mid;
        else
            left=mid+1;
    }
    return left;
}
int main(){
    int n,a[100];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    int m,b[100];
    scanf("%d",&m);
    for(int i=0;i<m;i++)
        scanf("%d",&b[i]);
    sort(a,a+n);
    int j=0,r;
    while(j<m){
        r=solve(a,0,n-1,b[j]) ;
        if(b[j]==a[r]){
            printf("YES\n");
        }
        else
            printf("NO\n");
        j++;
   }
    return 0;
}

发表于 2019-01-22 15:37:27 回复(0)

Benson666

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

int main(){
    int n,m;
    while(scanf("%d", &n)!=EOF){
        int a[10000];
        for(int i=0;i<n;i++){
            int tmp;
            cin>>tmp;
            a[tmp] = 1;
        }
        cin>>m;
        for(int i=0;i<m;i++){
            int tmp;
            cin>>tmp;
            if(a[tmp]==1) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
}

发表于 2018-03-19 16:17:55 回复(1)

C/C++

东子201803081322909

//有两点需要注意，一是yes和no的输出由token控制；二是如果例子中由两个测试数据需要用break跳出以免输出两个yes
#include <cstdlib>

#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{   int m,n,token=0;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
       scanf("%d",&a[i]);
    scanf("%d",&m);
   int b[m];
   for(int i=0;i<m;i++)
       scanf("%d",&b[i]);
   for(int i=0;i<m;i++){
       for(int j=0;j<n;j++){
           if(b[i]==a[j]){
           printf("YES\n");
           token=1;
           break;
           }
       }
       if(token==0)
       printf("NO\n");
       token=0;
   }

    system("PAUSE");
    return EXIT_SUCCESS;
}

发表于 2018-03-17 21:42:09 回复(0)

C/C++

叮哩当啷

哈希数组法：

//#include<stdio.h>
/*哈希数组每次需要初始化为0*/
#include<iostream>
#include<string.h>
using namespace std;
#define N 100000
int hashs[N];
int main()
{
int n,m,x;
while(cin>>n)
{
memset(hashs,0,sizeof(hashs));
for(int i=0;i<n;i++)
{
cin>>x;
hashs[x]=1;
}
cin>>m;
for(int i=0;i<m;i++)
{
cin>>x;
if(hashs[x]==1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
return 0;
}

编辑于 2018-01-14 18:06:16 回复(2)

rs勿忘初心

最简单的就是暴力循环比较搜索，需要注意的是谁跟谁比较。如下图，n和m的位置。

#include <iostream>
using namespace std;
int main( )
       {
         int m,n;
         while(cin>>n)
          {
           int a[n];
           for(int i=0;i<n;i++)
              cin>>a[i];
           cin>>m;
           int b[m];
           for(int j=0;j<m;j++)
               cin>>b[j];
           for(int i=0;i<m;i++)
            {
              for(int j=0;j<n;j++)
               {
                  if(b[i]==a[j])
                     {
                      cout<<"YES"<<endl;
                      break;
                     }
                  if(j==n-1)
                      cout<<"NO"<<endl; 
               }
            }
           }
           return 0;
         }

发表于 2017-04-19 19:32:55 回复(0)

karaysn

//我理解错了，原来是要拿第二个数组中的每个数和第一个数组中的数字比较

import java.util.Scanner;

public class Main { public static void main(String[] args) {

    Scanner sc=new Scanner(System.in);
    while(sc.hasNext()){
        //第一个数字，也是第一个数组的长度
        int a1=sc.nextInt();
        //定义第一个数组
        int[] a=new int[a1];
        for(int i=0;i<a.length;i++){
            a[i]=sc.nextInt();
        }

        //输入第二个数组的长度
        int b1=sc.nextInt();
        int[] b=new int[b1];
        for(int i=0;i<b.length;i++){
            b[i]=sc.nextInt();
        }

        for(int i=0;i<b.length;i++){
            test(b[i],a);
        }
    }
}

    public static void test(int a1,int[] a){
            boolean flag=false;
            while(!flag){
                for(int i=0;i<a.length;i++){
                    if(a[i]==a1){
                        System.out.println("YES");
                        flag=true;break;
                    }
                }
                break;
            }
            if(flag==false)
                System.out.println("NO");

    }

}

发表于 2017-04-17 10:32:32 回复(0)

查找

输入描述:

输出描述:

输入

输出

二分查找STL中bug-free实现

问题信息

热门推荐

通过挑战的用户

相关试题