Compute the intersection of two sorted arrays
https://github.com/epibook/epibook.github.io/blob/master/solutions/java/src/main/java/com/epi/IntersectSortedArrays3.javapublic static List<Integer> intersect(List<Integer> A, List<Integer> B) {
List<Integer> intersect = new ArrayList<>();
int i = 0;
int j = 0;
while (i < A.size() && j < B.size()) {
if (A.get(i).equals(B.get(j))
&& (i == 0 || !A.get(i).equals(A.get(i - 1)))) {
intersect.add(A.get(i));
++i;
++j;
} else if (A.get(i) < B.get(j)) {
++i;
} else { // A.get(i) > B.get(j).
++j;
}
}
return intersect;
}
O(mlogn)
public static List<Integer> intersect(List<Integer> A, List<Integer> B) {
List<Integer> intersect = new ArrayList<>();
for (int i = 0; i < A.size(); ++i) {
if ((i == 0 || !A.get(i).equals(A.get(i - 1)))
&& Collections.binarySearch(B, A.get(i)) >= 0) {
intersect.add(A.get(i));
}
}
return intersect;
}
O(mn)
public static List<Integer> intersect(List<Integer> A, List<Integer> B) {
List<Integer> intersect = new ArrayList<>();
for (int i = 0; i < A.size(); ++i) {
if (i == 0 || !A.get(i).equals(A.get(i - 1))) {
for (Integer b : B) {
if (A.get(i).equals(b)) {
intersect.add(A.get(i));
break;
}
}
}
}
return intersect;
}
