Find Intersection of Two Sets

暴力法

复杂度

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

思路

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

代码

public List<Integer> findByBruteForce(int[] arr1, int[] arr2){    List<Integer> res = new LinkedList<Integer>();    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<Integer> findBySortTogether(int[] arr1, int[] arr2){    List<Integer> res = new LinkedList<Integer>();    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, 10res:  1   res:  1res:  1res:  1

代码

public List<Integer> findBySortingAndMerge(int[] arr1, int[] arr2){    Arrays.sort(arr1);    Arrays.sort(arr2);    List<Integer> res = new LinkedList<Integer>();    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<Integer> findByBinarySearch(int[] arr1, int[] arr2){    List<Integer> res = new LinkedList<Integer>();    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<Integer> findByHashmap(int[] arr1, int[] arr2){    List<Integer> res = new LinkedList<Integer>();    HashSet<Integer> set = new HashSet<Integer>();    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;}