黑马程序员技术交流社区

标题: 数组问题！ [打印本页]

---

作者: 梁健    时间: 2011-12-10 10:26
标题: 数组问题！


两个1000个元素的数组，如何有效的找出他们的交集？

---

作者: ◇半度微凉    时间: 2011-12-10 11:06


如果说想要最有效，最高效的话，可以直接使用java已经提供的Arrays.sort(); 对数组进行排序， 然后再遍历数组，再把一个数组的元素在另外一个数组中2分查找，找到的元素就是两个数组的交集部分！
代码可以这样写：
int arr1[]={0,45,8,97,9,8·····};//数组arr1,里面1000个元素
int arr2[]={0,45,8,9,7,9,·····};//数组arr2,里面1000个元素

Arrays.sort(arr1);   
Arrays.sort(arr2);   
int len = arr1.length   
for (int i = 0; i < len; i++)   
{   
    if (Arrays.binarySearch(arr2, arr1) != -1)   //使用java提供的二元查找法 对数组元素进行查找 比较高效
         System.out.print (arr1);   
}  

---

作者: 小春同学    时间: 2011-12-10 11:31


因为不知数组中具体存储的数据类型，所以以下本人愚见：
1）数据量大，如果如果用两个for循环嵌套需开辟3个近似1000的空间，计算次数1000*1000=100万次；
2）利用TreeSet二叉排序树结构插入查询效率高的特点：将数组A存入TreeSet集合tsA中，将数组B存入TreeSet集合tsB中，这样保证两个数组里的所有元素唯一；然后再将tsB迭代存入tsA中，如果存入tsA中成功，这继续；失败了，证明相交，这将这个元素存入到数组C中。返回数组C。空间资源消耗还是比较大，但时间上很快大概最多4000次吧.少很多呀！愚见！

---

作者: t_mac    时间: 2011-12-10 12:13
先把数组中元素取出，再放到List集合中（必须遍历数组再往集合添加不能直接把数组转成集合），然后再利用List的retainall（）方法，我觉得这样做很简单。
简单演示一下吧：

import java.util.*;
public class TestArrayToCollection {
        public static void main(String[] args) {
                int[] a1 = {2,4,5,6};
                int[] a2 = {3,4,6,7};
               
                /*List<int[]> l1 = Arrays.asList(a1);
                List<int[]> l2 = Arrays.asList(a2);
                System.out.println(l1.contains(l2));*/注意这样直接转是不行的，因为直接利用Arrays.asList()方法转成集合，不能进行增删操作会抛
                                                                //UnsupportedOperationException异常
                List<Integer> l1 = new ArrayList<Integer>();
                List<Integer> l2 = new ArrayList<Integer>();
                for(int i=0;i<a1.length;i++){
                        l1.add(a1[i]);
                }
                for(int j=0;j<a2.length;j++){
                        l2.add(a2[j]);
                }
                System.out.println(l1);
                System.out.println(l2);
                l1.retainAll(l2);
                System.out.println(l1);//此时的l1即为要求结果
        }
}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2