acm 找球号(一）(大数据)

时间限制：3000 ms | 内存限制：65535 KB

难度：3

描述

在某一国度里流行着一种游戏。游戏规则为：在一堆球中，每个球上都有一个整数编号i(0<=i&lt;=100000000),编号可重复，现在说一个随机整数k(0<=k<=100000100)，判断编号为k的球是否在这堆球中（存在为"YES",否则为"NO"），先答出者为胜。现在有一个人想玩玩这个游戏，但他又很懒。他希望你能帮助他取得胜利。

输入

第一行有两个整数m，n(0<=n<=100000，0<=m<=1000000)；m表示这堆球里有m个球，n表示这个游戏进行n次。
接下来输入m+n个整数，前m个分别表示这m个球的编号i，后n个分别表示每次游戏中的随机整数k

输出

输出"YES"或"NO"

样例输入

6 4
23 34 46 768 343 343
2 4 23 343

样例输出

NO
NO
YES
YES

第一次做的时候没有考虑运行时间的问题，嵌套循环，结果超时，代码如下：

//package ACM;
//import java.util.*;
//
//public class Main
//{
//	public static void test(int[] m, int[]  n)
//	{
//		for(int ni = 0; ni < n.length; ni++)
//		{
//			for(int mi = 0; mi < m.length; mi++)
//			{
//				if(n[ni] == m[mi])
//				{
//					System.out.println("YSE");
//					break ;
//				}
//				if(mi == m.length - 1)
//					System.out.println("NO");
//			}
//		}
//		
//	}
//	public static void main(String[] args)
//	{
//		Scanner input = new Scanner(System.in);
//		int m;
//		int n;
//		m = input.nextInt();
//		n = input.nextInt();
//		int[] arrm = new int[m];
//		int[] arrn = new int[n];
//		for(int i = 0; i < m ; i++)
//		{
//			arrm[i] = input.nextInt();
//		}
//		for(int i = 0; i < n ; i++)
//		{
//			arrn[i] = input.nextInt();
//		}
//	test(arrm, arrn);
//		
//	}
//
//}

因为复杂度是N*M，导致超时，第二次用set，自动排序，还能剔除重复数据，应该能减少不少，试了下果然行了

package ACM;
import java.util.*;
public  class Main
{
	public static void main(String[] args)
	{
		Scanner input = new Scanner(System.in);
		int m , n;
		m = input.nextInt();
		n = input.nextInt();
		Set set = new HashSet();
		int mm;
		int nn;
		for(int i = 0; i < m ; i++)
		{
			mm = input.nextInt();
			set.add(mm);
		}
		for(int i = 0; i < n; i++)
		{
			nn = input.nextInt();
			if(set.contains(nn))
				System.out.println("YES");
			else
				System.out.println("NO");
			
		}
	}
}