題目
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Note:
Each element in the result must be unique.
The result can be in any order.
解法思路
- 先對
nums1去重，然后在和nums2取交集；
解法實(shí)現(xiàn)（一）使用基于平衡二叉樹實(shí)現(xiàn)的 TreeSet
- 對于
nums1來說，和nums2重復(fù)的元素要“移動”到交集中；
關(guān)鍵詞
Set TreeSet
時間復(fù)雜度
- O(NlogN)；
- 標(biāo)準(zhǔn)庫中的 Set 是基于平衡的二叉樹實(shí)現(xiàn)的，其時間復(fù)雜度為 O(logN)；
空間復(fù)雜度
- O(N)；
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
TreeSet<Integer> set = new TreeSet();
for (int num : nums1) {
set.add(num);
}
ArrayList<Integer> list = new ArrayList<>();
for (int num : nums2) {
if (set.contains(num)) {
list.add(num);
set.remove(num);
}
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
}
解法實(shí)現(xiàn)（二）使用基于哈希表實(shí)現(xiàn)的 HashSet
時間復(fù)雜度
- O(len(nums1)+len(nums2))；
空間復(fù)雜度
- O(len(nums1))；
關(guān)鍵詞
Set HashSet
import java.util.HashSet;
// 349. Intersection of Two Arrays
// https://leetcode.com/problems/intersection-of-two-arrays/description/
// 時間復(fù)雜度: O(len(nums1)+len(nums2))
// 空間復(fù)雜度: O(len(nums1))
public class Solution349 {
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> record = new HashSet<Integer>();
for(int num: nums1)
record.add(num);
HashSet<Integer> resultSet = new HashSet<Integer>();
for(int num: nums2)
if(record.contains(num))
resultSet.add(num);
int[] res = new int[resultSet.size()];
int index = 0;
for(Integer num: resultSet)
res[index++] = num;
return res;
}
private static void printArr(int[] arr){
for(int e: arr)
System.out.print(e + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums1 = {1, 2, 2, 1};
int[] nums2 = {2, 2};
int[] res = (new Solution349()).intersection(nums1, nums2);
printArr(res);
}
}
