Skip to content

Commit 6b64043

Browse files
Serena211Serena211
committed
may.11 common element
1 parent ae4b5ea commit 6b64043

6 files changed

Lines changed: 169 additions & 0 deletions

‎bin/Class99_Mix/CommonElementsInThreeSortedArray.class‎

1.49 KB
Binary file not shown.

‎bin/Class99_Mix/CommonNumbersOfTwoArrays1.class‎

2.5 KB
Binary file not shown.

‎bin/Class99_Mix/CommonNumbersOfTwoArrays2.class‎

2.99 KB
Binary file not shown.

‎src/Class99_Mix/CommonElementsInThreeSortedArray.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package Class99_Mix;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/*
7+
* Find all common elements in 3 sorted arrays.
8+
*
9+
* Assumptions
10+
* The 3 given sorted arrays are not null
11+
* There could be duplicate elements in each of the arrays
12+
*
13+
* Examples
14+
* A = {1, 2, 2, 3}, B = {2, 2, 3, 5}, C = {2, 2, 4}, the common elements are [2, 2]
15+
*/
16+
17+
public class CommonElementsInThreeSortedArray {
18+
public List<Integer> common(int[] a, int[] b, int[] c) {
19+
List<Integer> rsl = new ArrayList<Integer>();
20+
int aIdx = 0;
21+
int bIdx = 0;
22+
int cIdx = 0;
23+
while (aIdx < a.length && bIdx < b.length && cIdx < c.length) {
24+
if (a[aIdx] == b[bIdx] && b[bIdx] == c[cIdx]) {
25+
rsl.add(a[aIdx]);
26+
aIdx++;
27+
bIdx++;
28+
cIdx++;
29+
} else if (a[aIdx] < b[bIdx] || a[aIdx] < c[cIdx]) {
30+
aIdx++;
31+
} else if (b[bIdx] < a[aIdx] || b[bIdx] < c[cIdx]) {
32+
bIdx++;
33+
} else {
34+
cIdx++;
35+
}
36+
}
37+
return rsl;
38+
}
39+
40+
public static void main(String[] args) {
41+
CommonElementsInThreeSortedArray sol = new CommonElementsInThreeSortedArray();
42+
System.out.println(sol.common(new int[]{1,2,3,3},new int[]{2,3,4,4,5},new int[]{1,1,3,3}));
43+
}
44+
45+
}

‎src/Class99_Mix/CommonNumbersOfTwoArrays1.java‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package Class99_Mix;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.Collections;
6+
import java.util.HashSet;
7+
import java.util.List;
8+
9+
/*
10+
* Find all numbers that appear in both of the two unsorted arrays.
11+
*
12+
* Assumptions
13+
* Both arrays are not null.
14+
* There are no duplicate numbers in each of the two arrays respectively.
15+
*
16+
* Examples
17+
* A = {1, 2, 3}, B = {3, 1, 4}, return [1, 3]
18+
* A = {}, B = {3, 1, 4}, return []
19+
*/
20+
public class CommonNumbersOfTwoArrays1 {
21+
public List<Integer> common(List<Integer> a, List<Integer> b) {
22+
List<Integer> rsl = new ArrayList<Integer>();
23+
if (a.size() == 0 || b.size() == 0) {
24+
return rsl;
25+
}
26+
HashSet<Integer> set = new HashSet<Integer>();
27+
if (a.size() < b.size()) {
28+
for (Integer i : a) {
29+
set.add(i);
30+
}
31+
findCommon(rsl, set, b);
32+
} else {
33+
for (Integer i : b) {
34+
set.add(i);
35+
}
36+
findCommon(rsl, set, a);
37+
}
38+
Collections.sort(rsl);
39+
return rsl;
40+
}
41+
42+
private void findCommon(List<Integer> rsl, HashSet<Integer> set,
43+
List<Integer> b) {
44+
for (Integer i : b) {
45+
if (set.contains(i)) {
46+
rsl.add(i);
47+
}
48+
}
49+
}
50+
51+
public static void main(String[] args) {
52+
CommonNumbersOfTwoArrays1 sol = new CommonNumbersOfTwoArrays1();
53+
System.out.println(sol.common(Arrays.asList(5,1,3,2,4), Arrays.asList(4,2,3)));
54+
// java.util.Arrays.asList(5,1,3,2,4),java.util.Arrays.asList(4,2,3)
55+
}
56+
57+
}

‎src/Class99_Mix/CommonNumbersOfTwoArrays2.java‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
package Class99_Mix;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.Collections;
6+
import java.util.HashMap;
7+
import java.util.HashSet;
8+
import java.util.List;
9+
10+
/*
11+
* Find all numbers that appear in both of two unsorted arrays.
12+
*
13+
* Assumptions
14+
* Both of the two arrays are not null.
15+
* In any of the two arrays, there could be duplicate numbers.
16+
*
17+
* Examples
18+
* A = {1, 2, 3, 2}, B = {3, 4, 2, 2, 2}, return [2, 2, 3] (there are both two 2s in A and B)
19+
*/
20+
public class CommonNumbersOfTwoArrays2 {
21+
public List<Integer> common(List<Integer> a, List<Integer> b) {
22+
List<Integer> rsl = new ArrayList<Integer>();
23+
if (a.size() == 0 || b.size() == 0) {
24+
return rsl;
25+
}
26+
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
27+
if (a.size() < b.size()) {
28+
for (Integer i : a) {
29+
Integer count = map.get(i);
30+
if (count == null) {
31+
map.put(i, 1);
32+
} else {
33+
map.put(i, count + 1);
34+
}
35+
}
36+
findCommon(rsl, map, b);
37+
} else {
38+
for (Integer i : b) {
39+
Integer count = map.get(i);
40+
if (count == null) {
41+
map.put(i, 1);
42+
} else {
43+
map.put(i, count + 1);
44+
} }
45+
findCommon(rsl, map, a);
46+
}
47+
Collections.sort(rsl);
48+
return rsl;
49+
}
50+
51+
private void findCommon(List<Integer> rsl, HashMap<Integer, Integer> map,
52+
List<Integer> b) {
53+
for (Integer i : b) {
54+
Integer count = map.get(i);
55+
if (count != null && count != 0) {
56+
rsl.add(i);
57+
map.put(i, count - 1);
58+
}
59+
}
60+
}
61+
62+
public static void main(String[] args) {
63+
CommonNumbersOfTwoArrays2 sol = new CommonNumbersOfTwoArrays2();
64+
System.out.println(sol.common(Arrays.asList(5,1,3,2,2,2,4), Arrays.asList(4,2,2,3)));
65+
}
66+
67+
}

0 commit comments

Comments
 (0)