[Algo] Find Intersection of Two Sets 找交集

pf_miles 发布于2019-08-14 12:43 / 325人阅读

摘要：暴力法复杂度时间空间思路暴力解法，对于每个在集合中的元素，我们遍历一遍集合看看是否存在，如果存在则是。代码排序二分搜索复杂度时间空间思路将较短的那个集合排序，然后对于较长的集合中每一个元素，都在较短的集合中二分搜索相应的元素。

Find Intersection of Two Sets 暴力法 复杂度

时间 O(NM) 空间 O(1)

思路

暴力解法，对于每个在集合1中的元素，我们遍历一遍集合2看看是否存在，如果存在则是Intersection。

代码

public List findByBruteForce(int[] arr1, int[] arr2){
    List res = new LinkedList();
    for(int i = 0; i < arr1.length; i++){
        for(int j = 0; j < arr2.length; j++){
            if(arr1[i] == arr2[j]){
                res.add(arr1[i]);
            }
        }
    }
    return res;
}

统一排序法 复杂度

时间 O((M+N)log(M+N)) 空间 O(M+N)

思路

将两个集合合并起来排序，这样如果排序后的数组中有两个相同的元素，说明就是Intersection。

代码

public List findBySortTogether(int[] arr1, int[] arr2){
    List res = new LinkedList();
    int[] all = new int[arr1.length + arr2.length];
    System.arraycopy(arr1, 0, all, 0, arr1.length);
    System.arraycopy(arr2, 0, all, arr1.length, arr2.length);
    Arrays.sort(all);
    for(int i = 0; i < all.length - 1; i++){
        if(all[i] == all[i + 1]){
            res.add(all[i]);
            i++;
        }
    }
    return res;
}

排序归并法 复杂度

时间 O(MlogM+NlogN) 空间 O(1)

思路

将两个集合分别排序，用两个指针分别指向各自最小的元素。然后比较他们各自最小的元素，如果这两个元素相同，则加入结果中，并将两个指针都加1。否则哪个元素较小，则将其指针加1。

arr1: 1, 2, 8, 10 ==> arr1: 2, 8, 10 ==> arr1: 8, 10    ==> arr1: 8, 10 ==> ...
arr2: 1, 3, 9, 10     arr2: 3, 9, 10     arr2: 3, 9, 10     arr2: 9, 10
res:  1               res:  1            res:  1            res:  1

代码

public List findBySortingAndMerge(int[] arr1, int[] arr2){
    Arrays.sort(arr1);
    Arrays.sort(arr2);
    List res = new LinkedList();
    int i = 0, j = 0;
    while(i < arr1.length && j < arr2.length){
        if (arr1[i] == arr2[j]){
            res.add(arr1[i]);
            i++;
            j++;
        } else if (arr1[i] < arr2[j]){
            i++;
        } else if (arr1[i] > arr2[j]){
            j++;
        }
    }
    return res;
}

排序二分搜索 复杂度

时间 Min(O(MlogN+NlogN), O(NlogM+MlogM)) 空间 O(1)

思路

将较短的那个集合排序，然后对于较长的集合中每一个元素，都在较短的集合中二分搜索相应的元素。如果找到则加入结果中。之所以选择对较短的集合二分搜索，是因为排序需要NlogN的时间，如果对较长数组排序，假设N>M，则时间复杂度是NlogN+MlogN，而对较短数组排序，时间为MlogM+NlogM，显然(M+N)logN > (M+N)logM

代码

public List findByBinarySearch(int[] arr1, int[] arr2){
    List res = new LinkedList();
    if(arr1.length > arr2.length){
        int[] tmp = arr1;
        arr1 = arr2;
        arr2 = tmp;
    }
    Arrays.sort(arr1);
    for(int i = 0;i < arr2.length; i++){
        if(binarySearch(arr1, arr2[i])){
            res.add(arr2[i]);
        }
    }
    return res;
}

private boolean binarySearch(int[] arr, int target){
    int min = 0, max = arr.length - 1;
    while(min <= max){
        int mid = min + (max - min) / 2;
        if(arr[mid] == target){
            return true;
        } else if (arr[mid] > target) {
            max = mid - 1;
        } else {
            min = mid + 1;
        }
    }
    return false;
}

哈希表法 复杂度

时间 O(N) 空间 O(N)

思路

将第一个集合中的元素加入一个哈希表中，然后过一遍第二个集合，看是否存在于第一个集合中，因为用了哈希，所以总时间只要O(N)。

代码

public List findByHashmap(int[] arr1, int[] arr2){
    List res = new LinkedList();
    HashSet set = new HashSet();
    for(int i = 0; i < arr1.length; i++){
        set.add(arr1[i]);
    }
    for(int i = 0; i < arr2.length; i++){
        if(set.contains(arr2[i])){
            res.add(arr2[i]);
        }
    }
    return res;
}

云服务器服务器托管 Algo Intersection Sets two

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64654.html

前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
LintCode547/548_求数组交集不同解法小结

摘要：求数组交集不同解法小结声明文章均为本人技术笔记，转载请注明出处求数组交集要求元素不重复，给出两个数组，求二者交集且元素不重复，查找会超时解法一排序二分查找算法超时主要发生在大数组查找过程，因此采用二分查找提升查找效率，交集用保存实现去重解法 LintCode547/548_求数组交集不同解法小结 [TOC] 声明文章均为本人技术笔记，转载请注明出处：[1] https://segme...

gxyz 2019-08-16 10:34 评论0 收藏0
每周一练之数据结构与算法（Set）

摘要：一集合是什么与它相关数学概念有哪些解题集合定义集合是一种包含不同元素的数据结构。集合中的元素称为成员，集合最重要的两个特点集合中的成员是无序集合中不存在相同成员即无序且唯一。 showImg(https://segmentfault.com/img/remote/1460000019005270); 这是第四周的练习题，五一放假结束，该收拾好状态啦。下面是之前分享的链接： ...

silvertheo 2019-08-23 17:17 评论0 收藏0