现在有两个数组A以及B，长度分别是N，M。并且都是未经排序的。元素个数可能相同也可能相差很多。现在要求出他们的交集即公共元素，并说明时间复杂度和空间复杂度~
最普通的方法就是先排序然后进行比较。大家有没有更好的方法？
该问题被发起重新开启投票
投票剩余时间：
之前被关闭原因：
该问题被发起删除投票
投票剩余时间：
距离悬赏到期还有：
参与关闭投票者：
关闭原因：
该问题已经被锁定
锁定原因：（）
保护原因：避免来自新用户不合宜或无意义的致谢、跟帖答案。
该问题已成功删除，仅对您可见，其他人不能够查看。
方法一：如果是我来处理的话，可能我更偏向于使用一个位图，当然在c++中我记得应该有bitset这个东西，假设根据数组A建立一个位图，扫描数组A中的每个元素，将位图中的对应位置设置为1（当然如果数组A中存在重复元素的话，那么已经设置为1的地方就不需要重复设置）。当扫描完后，对应的位图也就设置完了。接下来，我们扫描数组B中的每个元素，然后根据元素值到之前建立好的位图中去查找，如果对应位置为1，那么表示这个是交集的一部分，并且记住要把设置为1的地方重新设置为0，因为可能存在重复元素，这样后面的重复元素就不会再重新放到交集集合中了。
时间复杂度，是o(M+N)空间复杂度的话，如果我们选的是数组A建立位图，那么空间复杂度就是数组A中的最大元素/8（Byte），如果选的是数组B建立位图，那么空间复杂度就是数组B中的最大元素/8(Byte)
缺点：如果数组A或只有两个元素【1，INT_MAX】，那么需要的空间复杂度就太高了，浪费了很多空间。针对上述方法的缺陷，可以考虑如下方法
方法二：扫描数组A中的每个元素，建立哈希表，对于冲突的部分，采用拉链法进行解决，然后和方法一一样扫描数组B中的每个元素，然后去查找对应的元素是否存在，并且做出相应的处理。在C++中的话，可以使用非标准库中的hashtable来解决。
时间复杂度是o(M+N)空间复杂度的话，根据STL中的介绍，这种复杂度不会太高，因为它是自适应的调整表的长度的。
方法三：使用STL中的set，这个的处理方法和上述类似时间复杂度:o(NlogN+MlogM) 空间复杂度：o(min(M,N)),set底层实现结构是红黑树，和你的节点个数有关吧
可能有些地方没考虑周到，希望有更多的人加入讨论当中！
版主看看我的方法，因为是求交集，所以可以想见这个程序的时间复杂度的下限是O（min(m,n)），这样我们可以把两个数组放在一起，合成一个数组，对这个合成的数组进行快速排序，由于快速排序是基于比较的排序算法，且当前两个数组中存放的是集合，所以不可能有重复的元素，也就是说，在快排的过程中，一旦遇到两个元素是相同的则可以认定这两个元素是交集中的元素；通过这种方式，实现时间复杂度为O(（m+n）lg(m+n))(PS:回避了遍历的过程，在比较的过程中直接产生交集)；而空间复杂度呢，若考虑另外开辟存储区进行存放的话，为O（m+n），但是可以考虑在原数组上进行原地排序，这样空间复杂度为O（1），这种方法理论上是可以实现的
我先给出一个例子来说明我的想法。
比如说数组A的元素集合为{2,5,6,7,3,4,2}，数组B的元素集合为{2,8,7}，各自集合中允许相同元素有重复，就好比A集合中的元素2是重复的。
先定义一个空的数组array，数组元素值全部为0，数组长度为max{M,N}。我先一个个处理A数组中的元素。拿到元素2，则把array数组下标为2的元素值赋值为1；拿到元素5，则把array数组下标为5的元素值赋值为1；就这样把A数组中的所有元素都处理完，此时数组array中，如果某个元素的值为1，就意味这对应的下标值出现在集合A中。
我再定义一个数组result，存放两个集合的交集。接着一个个处理B数组中的元素。拿到元素2，判断array[2] == 1，如果满足，则意味着元素2在A、B集合中都有，把元素2放到数组result中。拿到元素8，发现array[8] != 1，就意味着元素8不在A集合中。拿到元素7，发现array[7] == 1，则元素7在集合A、B中都有，把元素7放到数组result中。就这样一直处理完B集合中的元素，result数组中存储的值就是两个集合的交集。
空间复杂度：最多M+N，因为两个的交集元素个数最多是M个。时间复杂度：第一次处理A集合，需要处理N次，再次处理B集合，需要处理M次。M+N吧，不大确定对不对。
这样的话如果A的元素集合是{1,2,3,}，那么开辟的数组array将非常大，这样没有hash的效率高。
如果知道元素上限MaxElem的话，可以用bitmap，用两个bitmap，分别将两个数组中元素对应的位置1，最后将两个bitmap求与，得到的即为两个数组的交集，这里的空间复杂度为O(MaxElem)，时间复杂度为O(max(m,n))。
定义hashmap &元素，重复次数&
遍历长度短的数组a，hashmap[a[i]]++
遍历长度长的数组，if (hashmap.findkey(b[i]) != hashmap.end() && hashmap[b[i]] & 0) {把b[i] 加到结果中；hashmap[b[i]]--}
时间复杂度O(MAX(M, N)) 空间复杂度O(MIN(M, N))
虽然介绍的不如楼上同学的详细，但是仔细想了想还真没有什么更加有效的方法，能做到的就是先判断出两个数组的大小，然后把数据较少的那个当做参照，再一一遍历吧。我是新手，期待有更好的答案……
我用Java给你写了个代码，哈希就行了。
import java.util.HashMimport java.util.Mpublic class intersection {
public static void main(String[] args) {
Integer a[] = { 4, 7, 3, 6, 2 };
Integer b[] = { 9, 0, 5, 7, 3 };
Map&Integer, Integer& result = new HashMap&Integer, Integer&();
for (Integer item : a) {
if (result.get(item) != null) {
result.put(item, result.get(item) + 1);
result.put(item, 1);
for (Integer item : b) {
if (result.get(item) != null) {
result.put(item, result.get(item) + 1);
result.put(item, 1);
for (Map.Entry&Integer, Integer& item : result.entrySet()) {
Integer value = item.getValue();
if (value.equals(2)) {
System. out.println(item.getKey());
取较小的数组排序,然后遍历大数组,通过查找算法判断元素是否在小数组之中,如果在小数组之中则提取出来存入结果数组.
排序算法最好的复杂度为nlog(n),遍历为n,查找算法复杂度为log(n),实际复杂度=小数组排序复杂度nlog(n)+大数组遍历及小数组查找复杂度mlog(n)=mlog(n),其中m为较大数组长度,n为较小数组长度.实现过程中需要两个临时数组长度均为n,则空间复杂度为n,n为小数组长度.
我觉得可以考虑一下，把长的进行排序一下。然后遍历一遍短的，去长的中进行二分法查找，查找到的话就存入新的数组。不知道这样有没有更好一点。
这样的时间复杂度是O(max{NLen,MLen}log(max{NLen,MLen})log(min{NLen,MLen}))，效率较低。
最粗暴直接的算法是在每个A元素上遍历B元素，存在就写入一个新数组，这个算法时间复杂度是m的n次方，空间复杂度是是Max(M,N) +M + N + 32Bit * 2。由于不存在优化的可能，所以这基本是最差的方案。虽然不符合LZ要求，但是可以作为后面同学的标杆，算是我的一点点贡献吧。
不是您所需，查看更多相关问题与答案
德问是一个专业的编程问答社区，请
后再提交答案
关注该问题的人
共被浏览 (11509) 次匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。自己写两个判断字符串数组是否相等或数组内容是否相同，大家看下怎么改进下
　　在项目中经常用到判断两个数组经常相等，或者是判断数组内容是否相同（即排序后再判断是否相等）。想封装个方法方便日后使用。自己在这写了下，技术有限。大家看看还有什么地方可以改进，大家共同进步，呵呵。
　　代码如下
import java.util.A
import java.util.C
import java.util.L
public class Tool {
* 判断两个数组是否相等
boolean arrayIsEqual(String[] a, String[] b) {
if(a!=null&&b!=null){
if (a.length != b.length) {
for (int i = 0; i & a. i++) {
if(a[i]==null){
if(b[i]!=null){
if (!a[i].equals(b[i])) {
if(a==null&&b==null){
* 判断两个数组内容是否相同
boolean arraySortedIsEqual(String[] a, String[] b) {
if(a!=null&&b!=null){
List&String& tmpA=Arrays.asList(a);
List&String& tmpB=Arrays.asList(b);
Collections.sort(tmpA, new ComparatorString());
Collections.sort(tmpB, new ComparatorString());
return this.arrayIsEqual(tmpA.toArray(new String[tmpA.size()]), tmpB.toArray(new String[tmpB.size()]));
}else if(a==null&&b==null){
class ComparatorString implements Comparator&Object&{
public int compare(Object o1, Object o2) {
if(o1==null&&o2==null){
}else if(o1!=null&&o2!=null){
String s1=(String)o1;;
String s2=(String)o2;
pareTo(s2)&0){
if(o1==null){
public static void main(String[] args) {
Tool tool= new Tool();
String[] a = { "111", null, "444", "333" };
String[] b = { "111",
"444", "333" ,null};
String[] c = { "111", "222", "444", "333" };
System.out.println(tool.arrayIsEqual(a, b));
System.out.println(tool.arrayIsEqual(a, c));
System.out.println(tool.arraySortedIsEqual(a, b));
　　希望大家能提修改意见。
回答1：　　
回答2：　　完全不理解楼主这样的意义何在？java没有提供方法供楼主使用？ Arrays.equals&&&&&& 判断两个数组是否相等 Arrays.deepEquals&& 深度判断两个数组是否相等(比如你在数组中还有数组)
liuchen_hu
回答3：　　handong890 写道　　完全不理解楼主这样的意义何在？java没有提供方法供楼主使用？ Arrays.equals&&&&&& 判断两个数组是否相等 Arrays.deepEquals&& 深度判断两个数组是否相等(比如你在数组中还有数组)谢谢提醒啊。呵呵，主要还是基础不行
liuchen1983_