Merge two sorted array without duplicates
Question
Given two arrays, merge two sorted array without duplicates. Solve in a most efficient way.
Logic
- Compare first index element of both array and store the smaller one in the new array.
- Increment the index of array ( with a smaller number )
- Again compare elements of two array and store the least in new array.
Algorithm
- If array1 have small number, store that and increment the index of count array1.
- If the array2 have small number, store and increment the index count of array2.
- When we reach the end of an array, print the elements of another array.
- For example, if array1 is finished, store rest of elements of array2.
Program
#include<iostream.h> #include<stdlib.h> void main() { int *ar1,*ar2,*des,l,m,i,j,t=0; cout<<"enter length of two arrays\n"; cin>>m>>l; ar1 =(int*)malloc(l*sizeof(int)); // dynamic memory allocation based on the input ar2 = (int*)malloc(m*sizeof(int)); des =(int*)malloc((l+m)*sizeof(int)); cout<<"enter first array elements"; for(i=0;i<l;i++) cin>>ar1[i]; cout<<"enter second array elements"; for(i=0;i<m;i++) cin>>ar2[i]; if(ar1[l-1]<ar2[0]) //if the last element of ar1 is lesser than first element of ar2 { /* print ar1 first then ar2 */ for(i=0;i<l;i++) cout<<ar1[i]<<" "; for(j=0;j<m;j++) cout<<ar2[j]<<" "; } else if( ar2[m-1]<ar1[0]) //if the first element of ar1 is greater than last of ar2 { /* print ar2 first then ar1 */ for(j=0;j<m;j++) cout<<ar2[j]<<" "; for(i=0;i<l;i++) cout<<ar1[i]<<" "; } else // merge only if both above condition fail { i=0; j=0; while(i<l&&j<m) { if(ar1[i]<ar2[j]) { des[t]=ar1[i]; i++; //increment index of ar1, ar2 index unchanged t++; } else if(ar2[j]<ar1[i]) { des[t] =ar2[j]; j++; //increment index of ar2, ar1 index unchanged t++; } else // both are equal { des[t] =ar1[i]; i++; // increment both index j++; t++; } } while(i<l) // storing remaining of ar1 { des[t]= ar1[i]; t++; i++; } while(j<m) //storing remaining of ar2 { des[t] =ar2[j]; t++; j++; } for(i=0;i<t;i++) //merged array { cout<<des[i]<<" "; } } }
Alternative:
#include<stdio.h> void main() { int a[20],b[20],i,j,m,n,k,l=1; clrscr(); printf("enter the first array size:"); scanf("%d",&m); printf("enter the first array values:"); for(i=0;i<m;i++) { scanf("%d",&a[i]); } printf("enter the second array size:"); scanf("%d",&n); printf("enter the second array values :"); for(i=0;i<n;i++) { scanf("%d",&b[i]); } for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(b[i]==a[j]) //two numbers are equal then do nothing { l=0; break; } else if(b[i]<a[j]) //larger element found { l=0; for(k=m;k>j;k--) //swap the elements to insert b[i] { a[k]=a[k-1]; } m++; //increments the length of destination array a[j]=b[i]; //insert b[j] into a[] break; } } if(l==1) //all elements in b[] is greater than last element b[] { a[m]=b[i]; m++; }l=1; //act as a marker } for(i=0;i<m;i++) //prints the destination array { printf("%d ",a[i]); } getch(); }