[LintCode/LeetCode] Intersection of Two Arrays I & II [BitSet]

NO IMAGE

Problem

Given two arrays, write a function to compute their intersection.

Notice

Each element in the result must be unique.
The result can be in any order.

Example

Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Challenge

Can you implement it in three different algorithms?

Note

先想到的是HashSet(),其實HashMap也可以,只是需要在遍歷nums2的時候,新增到res陣列中的數要remove掉,略微麻煩了一點。在LC裡跑的時候,HashSet也要快一點。
另一種類似HashMap做法的BitSet()就快的多了。

Solution

HashSet

public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet();
Set<Integer> set2 = new HashSet();
List<Integer> ans = new ArrayList();
for (int i = 0; i < nums1.length; i  ) set1.add(nums1[i]);
for (int i = 0; i < nums2.length; i  ) {
if (set1.contains(nums2[i])) set2.add(nums2[i]);
}
int[] res = new int[set2.size()];
int index = 0;
for (Integer i: set2) res[index  ] = i;
return res;
}
}

BitSet

public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int[] res = new int[nums1.length];
if (nums1.length == 0 || nums2.length == 0) return new int[0];
int index = 0;
BitSet set = new BitSet();
for (int i = 0; i < nums1.length; i  ) {
set.set(nums1[i]);
}
for (int i = 0; i < nums2.length; i  ) {
if (set.get(nums2[i]) == true) {
res[index  ] = nums2[i];
set.set(nums2[i], false);
}
}
return Arrays.copyOfRange(res, 0, index);
}
}

Follow Up

如果是找出所有包括重複的截距呢?– Intersection of Two Arrays II

public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
int k = 0, l1 = nums1.length, l2 = nums2.length;
int[] result = new int[l1];
Arrays.sort(nums1);
Arrays.sort(nums2);
int i = 0, j = 0;
while (i < l1 && j < l2)
if (nums1[i] < nums2[j]) i  ;
else if (nums1[i] == nums2[j  ]) result[k  ] = nums1[i  ];
return Arrays.copyOf(result, k);
}
}