How can I merge 2 arrays?

Question

I am trying to merge 2 arrays in this way:

int[] arr1 = { 1, 3, 9, 5 };
int[] arr2 = { 7, 0, 5, 4, 3 };

now I need to create a new array that looks like this:

int[] merged = { 1, 3, 9, 5, 7, 0, 4 };

so I need to put all the numbers in the new array but if a number is in both arrays, then it shouldn't duplicate, every number should be only once in the merged array.

A number will never be twice or more in the same array.

this is the program that I built:

int[] arr1 = { 1, 6, -6, -9, 3, 4, -8, -7 };
int[] arr2 = { 5, 3, 2, 1, 70, 6, 7, -9, 99, 81 };

int counter = arr1.length;

boolean b = true;

for (int i = 0; i < arr1.length; i++) {
    for (int j = 0; j < arr2.length && b == true; j++) {
        if (arr1[i] == arr2[j])
            b = false;
    }

    if (b == true) {
        counter++;
    }

    b = true;
}

System.out.println(counter);

for some reason it doesn't work..

I am trying to write this program without built-in functions or lists, thank you.

Answer 1

Without using a List or Set or any third party library (Java 101 homework ready):

int[] arr1 = { 1, 6, -6, -9, 3, 4, -8, -7 };
int[] arr2 = { 5, 3, 2, 1, 70, 6, 7, -9, 99, 81 };

// Create a boolean array with the same length as the first array.
boolean[] duplicates = new boolean[arr1.length];
// Counter for how many duplicates we found.
int numDuplicates = 0;

// Loop through the first array and get all duplicates.
for (int i = 0; i < arr1.length; i++) {
    boolean duplicate = false;
    for (int j = 0; j < arr2.length; j++) {
        if (arr1[i] == arr2[j]) {
            duplicate = true;
            numDuplicates++;
            break;
        }
    }
    duplicates[i] = duplicate;
}

// The length of the merged array will be the two lengths subtracted by the number of
// duplicates we found.
int[] mergedArray = new int[arr1.length + arr2.length - numDuplicates];
int index = 0;

// loop through the first array. Don't add it to the merged array if it is a duplicate.
for (int i = 0; i < arr1.length; i++) {
    if (!duplicates[i]) {
        mergedArray[index] = arr1[i];
        index++;
    }
}

// loop through the second array and add all items.
for (int i = 0; i < arr2.length; i++) {
    mergedArray[index] = arr2[i];
    index++;
}

// optional. sort array
Arrays.sort(mergedArray);

System.out.println(Arrays.toString(mergedArray));

Output:

[-9, -8, -7, -6, 1, 2, 3, 4, 5, 6, 7, 70, 81, 99]

---

Using Set:

public static int[] mergeArrays(int[] arr1, int[] arr2) {
    Set<Integer> set = new HashSet<Integer>();
    for (int x : arr1) {
        set.add(x);
    }
    for (int x : arr2) {
        set.add(x);
    }
    int[] result = new int[set.size()];
    int index = 0;
    for (Iterator<Integer> it = set.iterator(); it.hasNext();) {
        result[index] = it.next();
        index++;
    }
    return result;
}

---

Using List:

public static int[] mergeArrays(int[] arr1, int[] arr2) {
    List<Integer> list = new ArrayList<Integer>();
    for (int i = 0, length = arr1.length; i < length; i++) {
        list.add(arr1[i]);
    }
    for (int i = 0, length = arr2.length; i < length; i++) {
        if (!list.contains(arr2[i])) {
            list.add(arr2[i]);
        }
    }
    int length = list.size();
    int[] result = new int[length];
    for (int i = 0; i < length; i++) {
        result[i] = list.get(i);
    }
    return result;
}

Answer 2

Without finding the bug in your code, I can see that you have a nested loop, which means the running time will be O(N^2).

You can get a better running time by sorting the two arrays O(Nlog(N)) and then merging them in a single iteration as is done in merge sort, eliminating the duplicates in the process. The total running time would be O(Nlog(N)).

Answer 3

As i understand you're trying to get count of unique items. Count only equal items. Then add array1 length and array2 length minus same item count. Try this:

    int [] arr1 = {1,6,-6,-9,3,4,-8,-7};
    int [] arr2 = {5,3,2,1,70,6,7,-9,99,81};

    int counter = 0;       

    for(int i=0; i<arr1.length; i++) {
        for(int j=0; j<arr2.length; j++) {
            Integer a1=arr1[i];
            Integer a2=arr2[j];
            if( (a1.equals(a2)) ){
                counter++;                  
            }
        }        
    }
    int counterLast=arr1.length+arr2.length-counter;

    System.out.println(counterLast);

Answer 4

Since you don't want duplicates, I recommend you use HashSet<Integer>.

//add elements from both arrays to the set
HashSet<Integer> set = new HashSet<Integer>();
for (int num : arr1)
    set.add(new Integer(num));

for (int num : arr2)
    set.add(new Integer(num));

// set will have one copy of each of elements in either arr1 and arr2
int[] result = new int[set.size()];
Iterator<Integer> set_iter = set.iterator();
for(int i = 0; set_iter.hasNext(); i++){
    result[i] = set_iter.next();
}
return result;

Here's more about HashSet: http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html Here's more about Iterator: http://docs.oracle.com/javase/7/docs/api/java/util/Iterator.html

Answer 5

Though you algorithm is very inefficient, but I think you have logical error in your code, the loop block should like this:

for(int i=0; i<arr2.length; i++) {
    for(int j=0; j<arr1.length; j++) {
        if(arr2[i] == arr1[j]) {
            b = false;
            break;
        }
    }
    if(b == true) {
        counter++;
    }
    b = true;
}

Answer 6

According To your code this program doesn't work well because two arrays are not the same size and your outer loop depend on the size of small array

for(int i=0; i arr1.length; i++)

so the program will end when it reach the size of small array. so if need this code run well you need to change the outer (depend on the size of large array) and inner loop depend on small array

int [] arr1 = {1,6,-6,-9,3,4,-8,-7}; int [] arr2 = {5,3,2,1,70,6,7,-9,99,81,55,4};

int counter = arr1.length;


boolean b = true;

for(int i=0; i<arr2.length; i++) {
    for(int j=0; j<arr1.length && b==true; j++) {
        if(arr2[i] == arr1[j])
        {
            b = false;
        }
    }

    if(b == true) {
        counter++;
    }

    b = true;
}

System.out.println(counter);
}

}

Answer 7

Using no collections and libraries

//Array copy complexity O(arr1.length + arr2.length)
int arr1Len = arr1.length;
int arr2Len = arr2.length;
int[] both = new int[arr1Len+arr2Len];
int[] result = new int[arr1Len+arr2Len];
System.arraycopy(arr1, 0, both, 0, arr1Len);
System.arraycopy(arr2, 0, both, arr1Len, arr2Len);

//Array sort complexity O(n) < x < O(n lg n)
Arrays.sort(both);

//Sorted array duplication removal O(n)
int counterUnique = 0;
result[0] = both[0];
for (int item : both) {
  if(result[counterUnique] != item){
    result[++counterUnique]=item;
  }
}
//optional
int[] rightSizeResult = Arrays.copyOf(result, counterUnique+1);

Demo

---

Using Sets

Hash set contains no duplicates. For each value hash is generated and it is used to access elements - for most cases you can be >99.99% sure that hash is unique. Hashset does not maintain order, to add this you can use LinkedHashSet.

You are not required to copy items in 1 array, you can just

Set<Integer> set = new HashSet<Integer>();
set.addAll(Arrays.asList(arr1));
set.addAll(Arrays.asList(arr2));
Integer[] result = set.toArray(new Integer[set.size()]);

Demo

---

Using Treeset

Treeset is order maintaining collection with no duplicates.

Collection<Integer> result = new TreeSet<Integer>(Arrays.asList(arr1));
result.addAll(Arrays.asList(arr2));

Demo

---

Nota Bene:

• I use type Integer and not int, this is because java generics do not work with primitive types.
• In production code, you would generally write this as:

Uses Google Guava lib

result = Sets.intersection(ImmutableSet.of(arr1), ImmutableSet.of(arr2));

There are several reasons for that, but most importantly you reduce potential problems that can occur during non atomic operation. In production code you mostly try to avoid primitive types and arrays (if you can). There are strong use cases for them, but that is out of scope of this question.

Answer 8

You could use SET which doesn't allow duplicated elements. I made it work with Only 1 loop.

    int[] arr1 = { 1, 6, -6, -9, 3, 4, -8, -7 };
    int[] arr2 = { 5, 3, 2, 1, 70, 6, 7, -9, 99, 81 };

    int maxLength = arr1.length >= arr2.length ? arr1.length : arr2.length;
    Set<Integer> merge = new HashSet<Integer>();
    for (int i=0; i<maxLength; i++) {
        if (i < arr1.length)
            merge.add(arr1[i]);
        if (i < arr2.length)
            merge.add(arr2[i]);
    }

    System.out.println(merge.toString());