forked from jin-zhe/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSetOperations.java
More file actions
134 lines (123 loc) · 3.17 KB
/
Copy pathSetOperations.java
File metadata and controls
134 lines (123 loc) · 3.17 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
import java.util.Arrays;
public class SetOperations {
public static void main(String[] args) {
int[] set1 = {1, 3, 2, 66, 23, 92, 8};
int[] set2 = {66, 8, 567, 1024, 512};
int[][] list = {{1, 3, 6, 2, 11},
{6, 44, 3, 1, 2},
{3, 44, 10, 2, 1},
{3, 2, 1, 44, 11}};
System.out.println("Intersection: " + Arrays.toString(intersect(set1, set2)));
System.out.println("Union: " + Arrays.toString(union(set1, set2)));
System.out.println("n-way intersection: " + Arrays.toString(nWayIntersect(list)));
}
/**
* Gets the intersection of two sorted lists
* @param arr1 list 1
* @param arr2 list 2
* @return intersection
*/
public static int[] intersect(int[] arr1, int[] arr2) {
int[] res = new int[arr1.length + arr2.length]; // result set
/* sort arrays */
Arrays.sort(arr1);
Arrays.sort(arr2);
int ptrRes = 0; // pointer for result set
int ptr1 = 0; // pointer for arr1
int ptr2 = 0; // pointer for arr2
while (ptr1 < arr1.length && ptr2 < arr2.length) {
int curr1 = arr1[ptr1];
int curr2 = arr2[ptr2];
/* if intersection found */
if (curr1 == curr2){
res[ptrRes] = curr1;
ptrRes++;
ptr1++;
ptr2++;
}
/* else if curr1 is lower */
else if (curr1 < curr2){
ptr1++;
}
/* else if curr2 is lower */
else{
ptr2++;
}
}
return Arrays.copyOfRange(res, 0, ptrRes);
}
/**
* Gets the union of two sorted lists
* @param arr1 list 1
* @param arr2 list 2
* @return union
*/
public static int[] union(int[] arr1, int[] arr2) {
int[] res = new int[arr1.length + arr2.length];
/* sort arrays */
Arrays.sort(arr1);
Arrays.sort(arr2);
int ptrRes = 0;
int ptr1 = 0;
int ptr2 = 0;
while (ptr1 < arr1.length || ptr2 < arr2.length) {
/* if both pointers have not ended */
if (ptr1 < arr1.length && ptr2 < arr2.length) {
int curr1 = arr1[ptr1];
int curr2 = arr2[ptr2];
/* if both values equal, take value and advance both pointers */
if (curr1 == curr2){
res[ptrRes] = curr1;
ptrRes++;
ptr1++;
ptr2++;
}
/* else take the lower value */
else if (curr1 < curr2){
res[ptrRes] = curr1;
ptrRes++;
ptr1++;
}
else{
res[ptrRes] = curr2;
ptrRes++;
ptr2++;
}
}
/* if pointer 2 ended */
else if (ptr1 < arr1.length){
res[ptrRes] = arr1[ptr1];
ptrRes++;
ptr1++;
}
/* if pointer 1 ended */
else{
res[ptrRes] = arr2[ptr2];
ptrRes++;
ptr2++;
}
}
return Arrays.copyOfRange(res, 0, ptrRes);
}
/**
* Performs intersection on a list of lists
* @param list list of n lists
* @return n-way intersection
*/
public static int[] nWayIntersect(int[][] list) {
return nWayIntersect(list, list.length - 1);
}
/**
* Recursively gets the intersection of list 0 to list i
* @param list list of lists
* @param i current list of interest
* @return intersection of lists 0 to i
*/
public static int[] nWayIntersect(int[][] list, int i) {
if (i == 1) { return intersect(list[0], list[1]); }
int[] currList = list[i];
Arrays.sort(currList);
int[] prevIntersections = nWayIntersect(list, i - 1);
return intersect(currList, prevIntersections);
}
}