Problem:
Start with two arrays of strings, A and B, each with its elements in alphabetical order and without duplicates. Return a new array containing the first N elements from the two arrays. The result array should be in alphabetical order and without duplicates. A and B will both have a length which is N or more. The best "linear" solution makes a single pass over A and B, taking advantage of the fact that they are in alphabetical order, copying elements directly to the new array.
mergeTwo({"a", "c", "z"}, {"b", "f", "z"}, 3) → {"a", "b", "c"}
mergeTwo({"a", "c", "z"}, {"c", "f", "z"}, 3) → {"a", "c", "f"}
mergeTwo({"f", "g", "z"}, {"c", "f", "g"}, 3) → {"c", "f", "g"}
Solution:
public String[] mergeTwo(String[] a, String[] b, int n) {
String out[] = new String[n];
int aindex =0, bindex=0;
for(int i=0; i<n; i++)
{
int cmp = a[aindex].compareTo( b[bindex] );
if(cmp<=0)
{
out[i] = a[aindex++];
if(cmp == 0) bindex++;
}
else
{
out[i] = b[bindex++];
}
}
return out;
}
public String[] mergeTwo(String[] a, String[] b, int n) {
ReplyDeleteString[] str = new String[a.length + b.length];
int ctr = 0;
for (String item : a) {
str[ctr] = item;
ctr++;
}
for (String value : b) {
str[ctr] = value;
ctr++;
}
List newstr = new ArrayList<>();
Collections.addAll(newstr, str);
newstr.sort(Comparator.naturalOrder());
ctr = 0;
String[] h = new String[n];
for (int i = 0; i < n; i++) {
if (!newstr.get(i).equals(newstr.get(i + 1))) {
h[ctr] = newstr.get(i);
ctr++;
}else{
n+=1;
if (n >= newstr.size()) {
n--;
h[ctr]=newstr.get(i);
}
}
}
return h;
}