mysql+两个数组交集_三种方法求解两个数组的交集
packagecom.Test;importjava.util.ArrayList;importjava.util.Arrays;importjava.util.HashMap;importjava.util.List;importjava.util.Map;//求两个数组的交集
public classFindIntersectionBetweenTwoArrays {//算法一：暴力搜索，时间复杂度O(n^2)，空间复杂度O(1)
public ArrayList getIntersection(int[] arr, int[] arr2) {
ArrayList res = new ArrayList();if(arr == null || arr.length == 0 || arr2 == null || arr2.length == 0) {returnres;
}for(int i = 0;i < arr.length;i ++) {int temp =arr[i];for(int j = 0;j < arr.length;j ++) {if(arr2[j] == temp && !res.contains(temp)) {
res.add(temp);break;
}
}
}returnres;
}//算法二：先排序，然后定义两个指针，时间复杂度O(nlogn) (排序)，空间复杂度O(1)
public ArrayList getIntersection2(int[] arr, int[] arr2) {
ArrayList res = new ArrayList();if(arr == null || arr.length == 0 || arr2 == null || arr2.length == 0) {returnres;
}
Arrays.sort(arr);
Arrays.sort(arr2);int i = 0;int j = 0;while(i < arr.length && j
i++;
}else if(arr[i] >arr2[j]) {
j++;
}else{if(!res.contains(arr[i])) {
res.add(arr[i]);
}
i++;
j++;
}
}returnres;
}//算法三：map计数，时间复杂度O(n)，空间复杂度O(n)，空间换时间
public ArrayList getIntersection3(int[] arr, int[] arr2) {
ArrayList res = new ArrayList();if(arr == null || arr.length == 0 || arr2 == null || arr2.length == 0) {returnres;
}
Map map = new HashMap();for(int i = 0;i < arr.length;i ++) {int key =arr[i];if(map.containsKey(key)) {int value =map.get(key);
value++;
map.put(key, value);
}else{
map.put(key,1);
}
}for(int i = 0;i < arr2.length;i ++) {int key =arr2[i];if(map.containsKey(key) && !res.contains(key)) {
res.add(key);
}
}returnres;
}public static voidmain(String[] args) {int[] arr = {1,2,5,3,3,4};int[] arr2 = {2,3,3,4,5,6};
FindIntersectionBetweenTwoArrays fb= newFindIntersectionBetweenTwoArrays();
List res =fb.getIntersection3(arr, arr2);
System.out.println(res);
}
}
————————————————
packagecom.Test;importjava.util.ArrayList;importjava.util.Arrays;importjava.util.HashMap;importjava.util.List;importjava.util.Map;//求两个数组的交集 public classFindIntersectionBetweenTwoArrays {//算法一：暴力搜索，时间复杂度O(n^2)，空间复杂度O(1) public ArrayList getIntersection(int[] arr, int[] arr2) { ArrayList res = new ArrayList();if(arr == null || arr.length == 0 || arr2 == null || arr2.length == 0) {returnres; }for(int i = 0;i < arr.length;i ++) {int temp =arr[i];for(int j = 0;j < arr.length;j ++) {if(arr2[j] == temp && !res.contains(temp)) { res.add(temp);break; } } }returnres; }//算法二：先排序，然后定义两个指针，时间复杂度O(nlogn) (排序)，空间复杂度O(1) public ArrayList getIntersection2(int[] arr, int[] arr2) { ArrayList res = new ArrayList();if(arr == null || arr.length == 0 || arr2 == null || arr2.length == 0) {returnres; } Arrays.sort(arr); Arrays.sort(arr2);int i = 0;int j = 0;while(i < arr.length && j i++; }else if(arr[i] >arr2[j]) { j++; }else{if(!res.contains(arr[i])) { res.add(arr[i]); } i++; j++; } }returnres; }//算法三：map计数，时间复杂度O(n)，空间复杂度O(n)，空间换时间 public ArrayList getIntersection3(int[] arr, int[] arr2) { ArrayList res = new ArrayList();if(arr == null || arr.length == 0 || arr2 == null || arr2.length == 0) {returnres; } Map map = new HashMap();for(int i = 0;i < arr.length;i ++) {int key =arr[i];if(map.containsKey(key)) {int value =map.get(key); value++; map.put(key, value); }else{ map.put(key,1); } }for(int i = 0;i < arr2.length;i ++) {int key =arr2[i];if(map.containsKey(key) && !res.contains(key)) { res.add(key); } }returnres; }public static voidmain(String[] args) {int[] arr = {1,2,5,3,3,4};int[] arr2 = {2,3,3,4,5,6}; FindIntersectionBetweenTwoArrays fb= newFindIntersectionBetweenTwoArrays(); List res =fb.getIntersection3(arr, arr2); System.out.println(res); } } ————————————————