51 lines
1.5 KiB
Java
51 lines
1.5 KiB
Java
import java.util.Arrays;
|
|
import java.util.BitSet;
|
|
import org.apache.commons.lang3.ArrayUtils;
|
|
|
|
public class OrderDisjointItems {
|
|
|
|
public static void main(String[] args) {
|
|
final String[][] MNs = {{"the cat sat on the mat", "mat cat"},
|
|
{"the cat sat on the mat", "cat mat"},
|
|
{"A B C A B C A B C", "C A C A"}, {"A B C A B D A B E", "E A D A"},
|
|
{"A B", "B"}, {"A B", "B A"}, {"A B B A", "B A"}, {"X X Y", "X"}};
|
|
|
|
for (String[] a : MNs) {
|
|
String[] r = orderDisjointItems(a[0].split(" "), a[1].split(" "));
|
|
System.out.printf("%s | %s -> %s%n", a[0], a[1], Arrays.toString(r));
|
|
}
|
|
}
|
|
|
|
// if input items cannot be null
|
|
static String[] orderDisjointItems(String[] m, String[] n) {
|
|
for (String e : n) {
|
|
int idx = ArrayUtils.indexOf(m, e);
|
|
if (idx != -1)
|
|
m[idx] = null;
|
|
}
|
|
for (int i = 0, j = 0; i < m.length; i++) {
|
|
if (m[i] == null)
|
|
m[i] = n[j++];
|
|
}
|
|
return m;
|
|
}
|
|
|
|
// otherwise
|
|
static String[] orderDisjointItems2(String[] m, String[] n) {
|
|
BitSet bitSet = new BitSet(m.length);
|
|
for (String e : n) {
|
|
int idx = -1;
|
|
do {
|
|
idx = ArrayUtils.indexOf(m, e, idx + 1);
|
|
} while (idx != -1 && bitSet.get(idx));
|
|
if (idx != -1)
|
|
bitSet.set(idx);
|
|
}
|
|
for (int i = 0, j = 0; i < m.length; i++) {
|
|
if (bitSet.get(i))
|
|
m[i] = n[j++];
|
|
}
|
|
return m;
|
|
}
|
|
}
|