有A，B两个整数集合，设计一个算法找出在A集合但不在B集合中的元素

题主试着做了一下，先给两个集合排序，然后分类讨论了好几种情况，把自己弄崩溃了，感觉智商很不够用。。。求助大神给个思路，如果有代码最好？

我这样分类讨论了好几种情况：

是不是思路跑偏了？

shell版本：
$ comm <(seq 5) <(seq 4 8) #加-23参数即可

算法嘛，要不要去看下人家的源码?

面试的话，用楼主采纳的方法比较好。如果用C++解决，可以用STL库中的集合求差集函数。好像是set_difference

PHP:
$a = [];
$b = [];
$r = [];
foreach($a as $v){

if(!in_array($v,$b)) 
    $r[] = $v;

}

Ruby:

a = [3, 5, 7]
b = [15, 10, 5, 0]
a - b  # => [3, 7]

感觉在耍赖……

这个现成的utils工具太多啦，找一找吧
Java工具包有：apache commons collections、Google guava等工具包
JavaScript：lodash、underscore

既然是集合的话，那就有一个潜在的前提，AB中的数字是不重复的。
整数要是数量不是很大的话，可以直接上位图，比如整数范围在65535内的，那就创建一个位图数组

char  A[65535];

初始化的时候全初始化为0，如果数字在A中存在，则对应的数组下标设置为1，比如1023在A中，则设置对应的下标

A[1023-1] = 1;

然后遍历看下B，将存在于A中的但不在B中的放到一个链表里即可。算法时间复杂度建A的时候为o(n),遍历B的时候为o(n),总体上仍为线性的。
建A的时候要考虑到A/B的整数范围，看以哪个为基准建立初始化位图开销最低。这是一个典型的空间换取时间的方法

如果是面试题的话，题主搜一下计数排序或者桶排序
如果解决工程问题，楼上的这些答案就行

$O(|A|log(|B|))$当然是很简单的。。
再优化的话，就对于每个 A 中的元素，在 B 中判断是否有就可以了。看似要$O(|A||B|)$，但是如果注意到了判断不存在的条件的单调关系，就可以$O(|A|+|B|)$解决。

这个是集合差运算，可以搜索一下实现代码

Java:

两个集合就是两个hashset，可以利用效率为O(1)的.contains()找出在两个set的交集，集合a删掉交集，剩下的集合a里的就是你要的结果了

public static HashSet<Integer> findValue(HashSet<Integer> setA, HashSet<Integer> setB) {

for (int num : setB) { //O(n)
    if (setA.contains(num)) {
        setA.remove(num); //O(1)
    }
}
return setA;

}

//overall time complexity: O(n)

最简单的方法就是循环遍历，

我不知道你是想什么语言来实现，c#中用Linq可以轻松实现你的需求；

var list = listA.Except(listB).ToList();

if java
set集合,利用特性:不能存储重复数据
添加重复数据的时候会返回flase

讲究效率的话，可以这样做。

1、可以将B集合里面的存在一个hash表当中，因为hash表找一个元素的时间复杂度是O(1);
2、在遍历A中元素,给一个伪代码:

for item in A:
    if item not in HASH(B):
        print item

Scala

利用原生函数

val a = Set(4,2,5,7)
val b = Set(1,2,4,5)
val c = a &~ b

repl下自己写

implicit class IntListMonid(l: List[Int]) {
    def quickSort(): List[Int] = {
         def qSort(l: List[Int]): List[Int] = l match {
            case Nil => Nil
            case head :: tail =>
                qSort(l.filter(head>_)) ::: head :: qSort(l.filter(head<_))
        }
        qSort(l)
    }
    
    def middle = l(l.length / 2)
    
    def binarySearch(searchValue: Int): Boolean = {
        def bSearch(l: List[Int], searchValue: Int): List[Int] = l match {
            case List(i) => if (i == searchValue) List(i) else Nil
            case List(_*) => 
                if (searchValue > l.middle) 
                    bSearch(l.take(l.middle), searchValue)
                else if (searchValue > l.middle) 
                    bSearch(l.drop(l.middle + 1), searchValue)
        }
        if (bSearch(l, searchValue) == Nil) false else true
    }
}

val al = a.toList
val bl = b.toList.quickSort
al filterNot bl.binarySearch

定义一个集合C，用集合A的元素对集合B的元素，进行遍历比较，如果集合A中当前的元素与集合B的每个元素都不相同，则将该元素放入集合C中；循环如此，直到用集合A的每一个元素遍历完集合B的每一个元素！

Python:

In [1]: a = {'1', '2', '3', '4', '5'}

In [2]: b = {'1', '2', '3'}

In [4]: a - b
Out[4]: {'4', '5'}

想这么多，这个问题根本的就是循环一个集合，看另一个集合里面有没有，只是着情的把某些步骤优化一下。。。

PHP

$a=array(1,2,3);
$b=array(2,3);
array_diff($a,$b);

PHP算法

    $a=array(1,5,3);
    $b=array(2,10,3);
    $f=true;
    $x=0;
    for($i=0;$i<count($a);$i++){
        for($k=0;$k<count($b);$k++){
            if($a[$i]==$b[$k]){
                $f=false;
            }
        }
        if($f){
            $c[$x++]=$a[$i];
        }
        
    }
    var_dump($c);
    die();

典型的求差集。楼主要什么语言的代码。

思路：对两个队列分别排序，再对两个有序队列进行归并排序。

题主采纳的答案说了数字小的时候的情况的处理方法，但是对数字大就得换种方法了。
其实可以对B建一棵树T，时间复杂度是nlogn，然后枚举A中每个元素，再到T中查询是否存在，复杂度是nlogn，这个方法的好处是，集合里面不一定是数字，甚至可以处理{1 2 hello P}类似这样的集合

我对Python和Ruby不熟，不知道是否有A-B的简单解决问题的方法，但是对于其他人的方法我不得不说，你们想的太复杂了。
我的想法很简单，将集合B连成一个字符串，然后循环A，若A中的元素对应的字符串不属于B连成的字符串，则该元素就是要找的元素。
例如：A={1,2,3,4,5};B={3,4,5,6,7};将B连成字符串bString="3-4-5-6-7";然后循环A，"1"不是这个字符串的一部分，则数字1就是我们要找的元素，数字2也是要找的元素，3、4、5不是。

其实不明白题注纠结什么，就是遍历两个集合啊，时间复杂度顶多就是O(m*n),以上很多都是可以解决的，其基本原理都用hash代替遍历，无非是空间换时间。不依靠其他工具包或工具包的话，个人赞成 @brzhang 的做法。如果B中的数据比较离散的话，只能对B中的数值hash之后再作key-value。之后遍历A就ok了！

List<T> A = new ArrayList<T>();
List<T> B = new ArrayList<T>();
A.removeAll(B);

做一个哈希表ht，key 为数组中的数，value 为一个 bool 标志位
遍历 B，对 i 属于 B，标志 ht[i] 为 true
遍历 A，对 i 属于 A，检查 ht[i]，所有 ht[i] 为 false 的元素即为所求

上面的方法大多只适合特殊领域，要么限定了数据特性，要么限定了语言。给出一个通用的方法。

利用集合的特性 A-B=(A+B)-B。

A+B很好算，重复的数据可以先不管。
由于A+B包含B，题主一开始考虑的方法就用上了，而且只有一种情况。先排序A+B，然后在A+B中二分搜索B中的数，删除就可以了。

优化一下，先判断一下A和B哪个大，二分搜索较大的集合。

以上方法较低效。大家不用考虑了，楼上有人提到用归并排序，是正确的。伪代码如下：

i=0,j=0;
res[];
while(i<lenght(A) && j<lenght(B)){
    if(A[i]<B[j]){
        i++;
        res.add(A[i]);
    }
    else if(A[i]==A[j]){
        i++;
        j++;
    }
    else{
        j++;
    }
}
if(i<lenght(A)){
    for(;i<lenght(A);++i){
        res.add(A[i]);
    }
}

【热门文章】