[Algo] Find Intersection of Two Sets 找交集

pf_miles 發布于2019-08-14 12:43 / 520人閱讀

摘要：暴力法復雜度時間空間思路暴力解法，對于每個在集合中的元素，我們遍歷一遍集合看看是否存在，如果存在則是。代碼排序二分搜索復雜度時間空間思路將較短的那個集合排序，然后對于較長的集合中每一個元素，都在較短的集合中二分搜索相應的元素。

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;
}

GPU云服務器云服務器 Algo Intersection Sets two

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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