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.

@AldourCheng I don't know what is a list yet, I need to do this only with what I learned so far (if,for,while, arrays, int and booleans — Ishay Frenkel
– Ishay Frenkel, Commented Jan 26, 2015 at 7:25

Jared Rummler · Accepted Answer · 2015-01-26 10:19:37Z

2

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;
}

edited Jan 26, 2015 at 10:19

answered Jan 26, 2015 at 7:31

Jared Rummler

38.2k21 gold badges137 silver badges149 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Ishay Frenkel Over a year ago

Thank you very much, is there a way I can do it without lists or built-in functions?

Jared Rummler Over a year ago

Yeah, it looks like this must be homework then :P. I'll modify my answer in a bit.

Jared Rummler Over a year ago

@IshayFrenkel Added an answer using no Lists.

Eran · Accepted Answer · 2015-01-26 07:14:35Z

1

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)).

answered Jan 26, 2015 at 7:14

Eran

395k57 gold badges726 silver badges793 bronze badges

Comments

sh4nkc · Accepted Answer · 2015-01-26 07:18:43Z

1

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

answered Jan 26, 2015 at 7:18

sh4nkc

3581 silver badge9 bronze badges

Comments

vmcloud · Accepted Answer · 2015-01-26 07:42:58Z

1

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;
}

edited Jan 26, 2015 at 7:42

answered Jan 26, 2015 at 7:22

vmcloud

6524 silver badges13 bronze badges

1 Comment

Ishay Frenkel Over a year ago

It doesn't works, counter is equals to 10 at the end of the program with int [] arr1 = {1,6,-6,-9,3,4,-8,-7}; int [] arr2 = {5,3,2,1,70,6,7,-9,99,81};

m.hassaballah · Accepted Answer · 2015-01-26 07:48:50Z

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);
}

}

Jemshit · Accepted Answer · 2015-01-26 07:51:52Z

1

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);

edited Jan 26, 2015 at 7:51

answered Jan 26, 2015 at 7:17

Jemshit

10.1k6 gold badges74 silver badges115 bronze badges

2 Comments

Ishay Frenkel Over a year ago

It doesn't work, it gives me the result of 76 with: int [] arr1 = {1,6,-6,-9,3,4,-8,-7}; int [] arr2 = {5,3,2,1,70,6,7,-9,99,81};

Jemshit Over a year ago

Ok i changed it, before that we counted second array's items multiple times which showed us bigger value.

Kingcesc · Accepted Answer · 2015-01-26 08:32:43Z

1

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());

answered Jan 26, 2015 at 8:32

Kingcesc

841 silver badge6 bronze badges

1 Comment

Jared Rummler Over a year ago

He cannot use Set (see bottom of question).

Community · Accepted Answer · 2020-06-20 09:12:55Z

1

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.

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Jan 26, 2015 at 8:17

Margus

20.1k15 gold badges59 silver badges104 bronze badges

4 Comments

Jared Rummler Over a year ago

The question clearly states that he doesn't want any duplicates and cannot use a List or Set (most likely homework).

Jared Rummler Over a year ago

your code is giving me compiling errors. I think a Set would probably be the way to go though.

Jared Rummler Over a year ago

The demo works great. Compile errors came from constructor not defined for TreeSet<Integer>(arr1) and HashSet<Integer>(arr1).

Margus Over a year ago

@JaredRummler Was writing from memory - now included working demo's. Code just needed Arrays.asList, because overload for array inputs has not been created.

Collectives™ on Stack Overflow

How can I merge 2 arrays?

8 Answers 8

3 Comments

Comments

Comments

1 Comment

Comments

2 Comments

1 Comment

Using no collections and libraries

Using Sets

Using Treeset

Nota Bene:

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

3 Comments

Comments

Comments

1 Comment

Comments

2 Comments

1 Comment

Using no collections and libraries

Using Sets

Using Treeset

Nota Bene:

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related