維護一個集合，支持如下幾種操作：
- “I x”，插入一個數x；
- “Q x”，詢問數x是否在集合中出現過；
現在要進行N次操作，對于每個詢問操作輸出對應的結果，
輸入格式
第一行包含整數N，表示運算元量，
接下來N行，每行包含一個操作指令，操作指令為”I x”，”Q x”中的一種，
輸出格式
對于每個詢問指令“Q x”，輸出一個詢問結果，如果x在集合中出現過，則輸出“Yes”，否則輸出“No”，
每個結果占一行，
資料范圍
1≤N≤1051≤N≤105
?109≤x≤109?109≤x≤109
輸入樣例：
5
I 1
I 2
I 3
Q 2
Q 5
輸出樣例：
Yes
No
N一般取大于運算元的第一個
質數
代碼：
import java.util.Arrays; import java.util.Scanner; public class Main{ static final int N=100003; static int e[]=new int[N]; static int ne[]=new int[N]; static int h[]=new int[N]; static int idx; static void insert(int x){//其實就是單鏈表的頭插法 int k=(x%N+N)%N;//x可能為負數，使它>=0 e[idx]=x; ne[idx]=h[k]; h[k]=idx; idx++; } static boolean find(int x){//其實就是遍歷鏈表 int k=(x%N+N)%N; for(int i=h[k];i!=-1;i=ne[i]) if(e[i]==x) return true; return false; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); int n=scan.nextInt(); Arrays.fill(h,-1); while(n-->0){ String op=scan.next(); int x=scan.nextInt(); if(op.equals("I")){ insert(x); } else{ if(find(x)) System.out.println("Yes"); else System.out.println("No"); } } } }
2.開放尋址法
基本思路：k=x%N ，如果這個位置沒有數就放在這個位置，否則依次尋找下一個位置
代碼：
import java.util.Arrays; import java.util.Scanner; public class Main{ static final int N=200003;//一般取資料范圍N的2倍 的 大于它的第一個質數 static int INF=(int)1e9+5; static int h[]=new int[N]; static int find(int x){ int k=(x%N+N)%N; while(h[k]!=INF && h[k]!=x){//這個位置有數并且不等于x k++;//尋找下一個位置 if(k==N) k=0;//找到最后一個位置，從頭開始尋找 } return k; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); Arrays.fill(h,INF);//初始化為一個不在資料范圍的數 int n=scan.nextInt(); while(n-->0){ String op=scan.next(); int x=scan.nextInt(); int k=find(x); if(op.equals("I")){ h[k]=x; } else{ if(h[k]!=INF) System.out.println("Yes"); else System.out.println("No"); } } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/98377.html
標籤：其他
下一篇：841. 字串哈希（hash）