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[n];
int count=0;
int acount=0;
int bcount=0;
while(count0){
str[count]=b[bcount];
count++;
bcount++;
}
else if(x<0){
str[count]=a[acount];
count++;
acount++;
}
else if(x==0){
str[count]=a[acount];
acount++;
bcount++;
count++;
}
}
return str;
}
there is no description for x..
Deletepublic String[] mergeTwo(String[] a, String[] b, int n) {
ReplyDeleteint pos =0, val =0, i =0, j =0;
String[] array = new String[n];
while (pos < array.length){
val = a[i].compareTo(b[j]);
if (val == 0){
array[pos++] = a[i];
i++;
j++;
}else if (val < 0){
array[pos++] = a[i];
i++;
}else if (val > 0){
array[pos++] = b[j];
j++;
}
}
return array;
}
public Strin[] mergeTwo(String[] a,String[] b,int n)
ReplyDelete{
HashSet set=new HashSet;
for(int i=0;i<a.length;i++)
set.add(a[i]);
for(int i=0;i<b.length;i++)
set.add(b[i]);
String str[]=set.toArray(new String[set.size()]);
String strArr[]=new String[n];
for(int i=0;i<n;i++)
strArr[i]=str[i];
return strArr;
}
public Strin[] mergeTwo(String[] a,String[] b,int n)
ReplyDelete{
HashSet set=new HashSet;
for(int i=0;i<a.length;i++)
set.add(a[i]);
for(int i=0;i<b.length;i++)
set.add(b[i]);
String str[]=set.toArray(new String[set.size()]);
String strArr[]=new String[n];
for(int i=0;i<n;i++)
strArr[i]=str[i];
return strArr;
}
public Strin[] mergeTwo(String[] a,String[] b,int n)
ReplyDelete{
HashSet set=new HashSet;
for(int i=0;i<a.length;i++)
set.add(a[i]);
for(int i=0;i<b.length;i++)
set.add(b[i]);
String str[]=set.toArray(new String[set.size()]);
String strArr[]=new String[n];
for(int i=0;i<n;i++)
strArr[i]=str[i];
return strArr;
}
i didn't readthath A and B has the same length. My solution in that case...
ReplyDeletepublic String[] mergeTwo(String[] a, String[] b, int n) {
String [] x =new String[n];
String [] y = new String [a.length +b.length];
for (int i=0; i<a.length; i++) {
y[i] = a[i];
}
for (int i=0; i<b.length; i++) {
y[a.length +i] = b[i];
}
Arrays.sort(y);
for (int q=0; q<y.length-1; q++) {
if(y[q].equals(y[q+1])) {
y[q]="zzzzzzz";
}
}
Arrays.sort(y);
for(int w=0; w<n; w++) {
x[w]=y[w];
}
return x;
ReplyDeletepublic String[] mergeTwo(String[] a, String[] b, int n)
{
ArrayList merge = new ArrayList();
String[] result = new String[n];
for(int s = 0; s < a.length; s++)
{
merge.add(a[s]);
}
for(int x = 0; x < b.length; x++)
{
merge.add(b[x]);
}
Collections.sort(merge);
for(int r = 0; r < merge.size() - 1; r++)
{
if(merge.get(r).equals(merge.get(r + 1)))
{
merge.remove(r);
}
}
for(int i = 0; i < n; i++)
{
result[i] = merge.get(i);
}
return result;
}
ArrayList with triangle brackets are removed for some reason.
Deletepublic String[] mergeTwo(String[] a, String[] b, int n)
Delete{
ArrayList merge = new ArrayList();
String[] result = new String[n];
for(int s = 0; s < a.length; s++)
{
merge.add(a[s]);
}
for(int x = 0; x < b.length; x++)
{
merge.add(b[x]);
}
Collections.sort(merge);
for(int r = 0; r < merge.size() - 1; r++)
{
if(merge.get(r).equals(merge.get(r + 1)))
{
merge.remove(r);
}
}
for(int i = 0; i < n; i++)
{
result[i] = merge.get(i);
}
return result;
}
public String[] mergeTwo(String[] a, String[] b, int n) {
ReplyDeleteString[] res = Arrays.copyOfRange(a, 0, n);
for(int i = 0; i < b.length; i++){
for(int y = 0 ; y < res.length; y++){
if(y > 0 && b[i].compareTo(res[y-1]) == 0) break;
if(b[i].compareTo(res[y]) < 0){
String repl = res[y];
res[y] = b[i];
if(y+1 < res.length) res[y+1] = repl;
break;
}
}
}
return res;
}
public String[] mergeTwo(String[] a, String[] b, int n) {
ReplyDeleteList list = new ArrayList();
for(int i = 0;i<n;i++){
if(!list.contains(a[i]))list.add(a[i]);
if(!list.contains(b[i]))list.add(b[i]);
}
Collections.sort(list);
return list.subList(0,n).toArray(new String[n]);
}
public String[] mergeTwo(String[] a, String[] b, int n) {
ReplyDeleteString[] arr = new String[n];
for (int i = 0, j = 0, arrPlace = 0 ; arrPlace < arr.length; ) {
char one = (char) Math.min(a[i].charAt(0), b[j].charAt(0));
arr[arrPlace] = "" + one;
arrPlace++;
if (a[i].charAt(0) < b[j].charAt(0)) i++;
else if (a[i].charAt(0) > b[j].charAt(0)) j++;
else {
i++;
j++;
}
}
return arr;
}
Linear solution using the concept of Merge Sort:
ReplyDeletepublic int commonTwo(String[] a, String[] b) {
int count=0;
int i=0,j=0;
Set set = new HashSet();
while( i< a.length && j < b.length){
int cmp = a[i].compareTo(b[j]);
if(cmp == 0){
if(!set.contains(a[i])){
set.add(a[i]);
count++;
}
i++;
j++;
}
else if(cmp < 0)
i++;
else
j++;
}
return count;
}
public String[] mergeTwo(String[] a, String[] b, int n) {
ReplyDeleteString[] out = new String[n];
int aIndex = 0, bIndex = 0;
for(int i = 0; i < n; i++) {
if(a[aIndex].compareTo( b[bIndex] ) <= 0) {
out[i] = a[aIndex++];
if(out[i].compareTo( b[bIndex]) == 0) {
bIndex++;
}
} else {
out[i] = b[bIndex++];
}
}
return out;
}
public String[] mergeTwo(String[] a, String[] b, int n) {
ReplyDeleteString[] copy = Arrays.copyOfRange(a, 0, n);
for (final String s : b) {
int j = 0;
while (j < copy.length) {
if (j > 0 && s.compareTo(copy[j - 1]) == 0) {
break;
}
if (s.compareTo(copy[j]) < 0) {
String result = copy[j];
copy[j] = s;
if (j + 1 < copy.length) {
copy[j + 1] = result;
break;
}
}
j++;
}
}
return copy;
}
public String[] mergeTwo(String[] a, String[] b, int n) {
ReplyDeleteList list = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (!list.contains(a[i])) list.add(a[i]);
if (!list.contains(b[i])) list.add(b[i]);
}
Collections.sort(list);
return list.subList(0,n).toArray(new String[n]);
}
public String[] mergeTwo(String[] a, String[] b, int n) {
ReplyDeleteTreeSet myTreeSet = new TreeSet();
Collections.addAll(myTreeSet,a);
Collections.addAll(myTreeSet,b);
return Arrays.copyOfRange(myTreeSet.toArray(new String[n]), 0, n);
}
public String[] mergeTwo(String[] a, String[] b, int n) {
ReplyDeletereturn java.util.stream.Stream.concat(Arrays.stream(a),Arrays.stream(b)).distinct().sorted().limit(n).toArray(String[]::new);
}
public String[] mergeTwo(String[] a, String[] b, int n) {
ReplyDeleteString[] result = new String[n];
int index_a = 0;
int index_b = 0;
for (int i = 0; i < n; i++) {
if (a[index_a].compareTo(b[index_b]) == 0) {
result[i] = a[index_a];
index_a++;
index_b++;
} else if (a[index_a].compareTo(b[index_b]) > 0) {
result[i] = b[index_b];
index_b++;
} else if (a[index_a].compareTo(b[index_b]) < 0) {
result[i] = a[index_a];
index_a++;
}
}
return result;
}