偶遇算法1

1、问题描述：

有两组随机生成的（0～99999）Int32数据A和B，将A按顺序判断在B中是否存在并记录在Boolean型的C中

2、解决思路：

A数组:不管，随意，也不用排序,

B数组：[5，2，4，1],假设最大为5，注意没有3

初始化一个长度为5（最大数）的布尔数组:a[1],[2],[3],[4],[5]

循环B,将B中值作为a的下标，对应位置标记为true，例如

a[5]= true;

a[2]= true;

a[4]= true;

a[1]= true;

注意a[3]没有，为false

最后循环A，直接对比下标，如果A={2，3},那么：

a[2]=true,说明存在，则C[2]=true，到C中标记true

a[3]=false，则没有。C中标记为false

如果你最大为99999,那么这个数组要这么长你可以直接设置为99999，浪费一点空间；

3.、代码实现：

public static void main(String[] args) {

//B数组：[5，2，4，1]

            Random rand =new Random();

            int maxValue =120000;//假定A和B 的最大值

            int length =70000;//a，b 的长度

            int [] a =new int[length];

            int [] b =new int[length];

            boolean[] c=new boolean[length];

            boolean[] temp =new boolean[maxValue];

            //随机初始化啊a,b数组

            for(int i =0;i

a[i] = rand.nextInt(maxValue);

                    b[i] = rand.nextInt(maxValue);

                }

long t1 = System.currentTimeMillis();

            //循环B，验证元素是否存在(循环B,将B中值作为a的下标，对应位置标记为true)

            for (int item : b) {

temp[item] =true;

                }

for(int i =0;i

if(temp[a[i]])

c[i] =true;

                }

long t2 = System.currentTimeMillis();

            System.out.println(t2-t1);

        }

本机测试用时1到2ms