快速判断两个有限集合是否存在交集

先将一个集合存入Map数据结构中
然后依次从Map中去取另一个集合中的元素
如果取得到，说明存在交集
利用了数组的随机存取特性，匹配速度很快，时间复杂度是两个集合的大小之和。

    /**
     * 快速判断两个集合是否存在交集
     * 时间复杂度：2n
     */
    @Test
    public void testJiaoji() {
        String[] aa = new String[]{"datou", "xiaoming", "xiaohua", "xiaohong"};
        String[] bb = new String[]{"dawei", "daming", "dahua", "dahong", "datou"};
        Map<String, String> map = new HashMap<>();
        for(String item : aa) {
            map.put(item, "1");
        }

        boolean flag = false;
        for(String item : bb) {
            if (map.get(item) != null) {

                flag = true;
                break;
            }
        }

        if(flag) {
            System.out.println("存在交集");
        } else {
            System.out.println("不存在交集");
        }

    }


打印结果

存在交集

概念：集合是由一组无序且唯一（每个元素只出现一次）的项组成的一组数据。其与数学里的集合是同一个概念。在ES6里已经引入了集合的数据结构概念——Set类。

分类：常见的有空集，并集，交集，差集。

应用场景：1）数据去重；2）用于存储一些独一无二的数据。

js实现一个集合

集合的特性类似于JavaScript数据类型里的Object，Object对象里的每个键都是唯一。下面用一个名为item的对象表示集合去实现一个简单的集合类。其中集合里的元素是以{value:value}值值对的形式存储的

定义Skipper类，表示集合，其中包含了如下几个操作方法（为了方便阅读，已把方法从类里提取出来展示）

class Skipper{
    constructor(){
        this.item = {};    // 一个集合(值值对，如value : value)
    }
}

查找元素方法

    has(element){           
        return this.item.hasOwnProperty(element);
    }

新增元素方法

    add(element){           
        if(!this.has(element)){
            this.item[element] = element;
            return 'success';
        }else{
            return '该元素已存在';
        }
    }

删除元素方法

    remove(element){        
        if(this.has(element)){
            delete this.item[element];
            return 'success';
        }else{
            return '该元素不存在';
        }
    }

清空元素方法

    clear(){                
        this.item = {};
    }

查看集合大小

    size(){                
        return Object.keys(this.item).length;    // 由item对象的键组成的数组的长度
    }
   

提取集合所有元素并组合成的一个数组

    values(){               
        let arr = [];
        for(let key in this.item){
            arr.push(this.item[key]);
        }
        return arr;
    }

查看完整源码

 

并集类

给定两个集合A，B，把他们所有的元素合并在一起组成的集合，叫做集合A与集合B的并集，记作A∪B，读作A并B。

class Union{
    getSkipper(A,B){
        let result = new Skipper();
        A.values().forEach(element=>{            // 遍历第一个集合
            result.add(element);   // add()已去重
        });
        B.values().forEach(element=>{       // 遍历第二个集合
            result.add(element);
        });
        return result;
    }
}

交集类

设A，B是两个集合，由所有属于集合A且属于集合B的元素所组成的集合，叫做集合A与集合B的交集（intersection），记作A∩B。

class Intersection{
    getSkipper(A,B){
        let result = new Skipper()
        A.values().forEach(element=>{
            if(B.has(element)){
                result.add(element);    
            }
        });
        return result
    }
}

补集类

由A中所有不属于B的元素组成的集合，叫集合B在A中的补集，又称差集。

class Difference{
    getSkipper(A,B){
        let result = new Skipper();
        A.values().forEach(element=>{
            if(!B.has(element)){
                result.add(element);
            }
        });
        return result;
    }
}

更多数据结构相关，请查看专栏：《JavaScript数据结构与算法》

（完）

计算 两个集合的交集、并集、差集、对称集

import sys
import time


#刷新缓冲区
def flush():
    time.sleep(1)

#除去重复元素
def duplicate_removal(lt):
    lt1 = []
    for i in lt:
        if i not in lt1:
            lt1.append(i)
    return lt1

#并集计算
def union():
    tmp = [var for var in line_A if var in line_B]
    return tmp


#对称差的计算
def Symmetric_difference(list_A, list_B):
    sym_list = []
    for item in list_A:
        if item not in list_B:
            sym_list.append(item)
    for item in list_B:
        if item not in list_A:
            sym_list.append(item)

    return sym_list


#差集获取
def Difference_set(list_A, list_B):
    ret_list = []
    for item in list_A:
        if item not in list_B:
            ret_list.append(item)
    # for item in line_B:
    #     if item not in line_Ai:
    #         ret_list.append(item)
    return  ret_list

i = int(0)
print("请输入集合{0}的各个元素".format("A" if(i == 0) else "B"))
line_A = list(map(str, sys.stdin.readline().strip().split()))
flush()
line_A = duplicate_removal(line_A)

i += 1
print("请输入集合{0}的各个元素".format("A" if (i == 0) else "B"))
line_B = list(map(str, sys.stdin.readline().strip().split()))
flush()
line_B = duplicate_removal(line_B)




#显示两个集合的数据
print("集合A：{0}\n集合B：{1}".format(line_A if (line_A != []) else "line_A 为空集",
                                line_B if (line_B != []) else "line_B 为空集"))

print("A∪B：{0}".format(duplicate_removal(line_A + line_B)))

print("A∩B：{0}".format(union()))

print("A-B: {0}".format(Difference_set(line_A, line_B)))

print("A⊕B: {0}".format(Symmetric_difference(line_A, line_B)))

#答案
#请输入集合A的各个元素
1231 465467 984 654
请输入集合B的各个元素
654 123 41654 6789 45
集合A：['1231', '465467', '984', '654']
集合B：['654', '123', '41654', '6789', '45']
A∪B：['1231', '465467', '984', '654', '123', '41654', '6789', '45']
A∩B：['654']
A-B: ['1231', '465467', '984']
A⊕B: ['1231', '465467', '984', '123', '41654', '6789', '45']

Process finished with exit code 0

#
#
#


 

 

 



 





 


 

共回答了9个问题采纳率：100%
伪代码如下
void main()
{
int a[10];
int b[10];
输入a和b的值
调用子函数
switch (子函数)
{
case 返回值:
``` ```
}
}
写个子函数
int compare(int a[], int b[])
{
int count = 0;//用于存储a和b相等元素个数
int flag = 0;//用于判断是否有不等元素
int i, j;
for(i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
for(j = 0; j < sizeof(a) / sizeof(a[0]); j++)
{
if(b[j] == a[i])
{
count++;
break;
}
}
//此时已遍历到b[]的末尾，没有与a[i]相等的元素
if(b[j] != a[i] count != sizeof(b) / sizeof(b[0]))
flag = 1;
}
if(count == 10)
return 1;//元素全等
/*包含和交集的区别在于两数组间是否有不同的元素*/
if(count != 10 count != 0)
{
if(flag == 0)
return 2;//元素不全相等,且没有不相等的元素，为包含
else
return 3;//交集
}
if(count == 0)
return 4;//没相等元素，无交集
}
1年前
6