交集是集合里的概念，而集合是不允許有重復元素的，然而數組卻是允許重復元素的。
所以解這道題時要注意去重。
使用HashSet
這無疑是最簡單，最取巧的方法。通過把一個數組放入HashSet中，然后再遍歷第二個數組看元素是否存在于HashSet里即可找出交集，時間復雜度為 O(n) + O(m), n和m為兩個數組的長度
//使用HashSet
public static Integer[] find2(int[] arr1, int[] arr2) {
Set<Integer> resultSet = new HashSet<Integer>();
//HashSet存取的時間復雜度都為O(1)
Set<Integer> set = new HashSet<Integer>();
for(int num : arr1){
set.add(num);
}
for(int num : arr2){
if(set.contains(num)){
resultSet.add(num);
}
}
return resultSet.toArray(new Integer[resultSet.size()]);
}
放入一個數組，排序，找相鄰是否相同
- 把兩個數組分別去重后，放入一個數組， O(m+n)
- 排序 O((m+n) * log2(m+n))
- 遍歷，相鄰元素相同即為交集元素 O(m+n)
//合并成一個數組，排序后遍歷，相鄰相同即為交集元素
public static Integer[] find3(int[] arr1, int[] arr2) {
Set<Integer> resultSet = new HashSet<Integer>();
//給兩個數組去重，合并
Set<Integer> set1 = new HashSet<Integer>();
for(int num : arr1){
set1.add(num);
}
Set<Integer> set2 = new HashSet<Integer>();
for(int num : arr2){
set2.add(num);
}
List<Integer> list = new ArrayList<Integer>();
list.addAll(set1);
list.addAll(set2);
Integer[] newArr = list.toArray(new Integer[list.size()]);
//排序
Arrays.sort(newArr);
//遍歷一遍,相鄰相同即是交集
Integer previous = null;
for(Integer current : newArr){
if(previous == current){
resultSet.add(previous);
}
previous = current;
}
return resultSet.toArray(new Integer[resultSet.size()]);
}
分別排序，交叉查找
- 分別排序, O(n*log2n) + O(m*log2m)
- 交叉查找, O(n+m)
//對兩個數組排序，然后交叉查找
public static Integer[] find1(int[] arr1, int[] arr2) {
//排序
Arrays.sort(arr1);
Arrays.sort(arr2);
Set<Integer> resultSet = new HashSet<Integer>();
int indexOfArr1 = 0;
int indexOfArr2 = 0;
while (indexOfArr1 < arr1.length && indexOfArr2 < arr2.length) {
//從數組1中取出一個元素，逐一和數組2的元素比較，直到數組2的元素大于這個取出的元素
int benchMarkInArr1 = arr1[indexOfArr1];
for ( ; indexOfArr2 < arr2.length; indexOfArr2++) {
if(benchMarkInArr1 == arr2[indexOfArr2]){
resultSet.add(benchMarkInArr1);
}else if(benchMarkInArr1 < arr2[indexOfArr2]){
break;
}
}
//數組1坐標后移一位
indexOfArr1 = indexOfArr1 + 1;
if(indexOfArr1 >= arr1.length || indexOfArr2 >= arr2.length){
//任意數組已經遍歷到頭，那不再可能有更多的交集元素
break;
}
//從數組2中取出一個元素，逐一和數組1的元素比較，直到數組1的元素大于這個取出的元素
int benchMarkInArr2 = arr2[indexOfArr2];
for ( ; indexOfArr1 < arr1.length; indexOfArr1++) {
if(benchMarkInArr2 == arr1[indexOfArr1]){
resultSet.add(benchMarkInArr2);
}else if(benchMarkInArr2 < arr1[indexOfArr1]){
break;
}
}
}
return resultSet.toArray(new Integer[resultSet.size()]);
}
比起上一種解法，O(n*log2n) + O(m*log2m) 應該小于 O((m+n) * log2(m+n))，所以時間復雜度會低一些
