Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Checking if two int arrays have duplicate elements, and extract one of the duplicate elements from them

I'm trying to write a method, union(), that will return an int array, and it takes two int array parameters and check if they are sets, or in other words have duplicates between them. I wrote another method, isSet(), it takes one array argument and check if the array is a set. The problem is I want to check if the two arrays in the union method have duplicates between them, if they do, I want to extract one of the duplicates and put it in the unionArray[] int array. This is what I tried so far.

public int[] union(int[] array1, int[] array2){
  
  int count = 0;
  if (isSet(array1) && isSet(array2)){
     for (int i = 0; i < array1.length; i++){
        for (int j = 0; j < array2.length; j++){
           if (array1[i] == array2[j]){ 
              System.out.println(array2[j]);
              count ++;
           }
        }
     }
  }
  int[] array3 = new int[array2.length - count];
     
  int[] unionArray = new int[array1.length + array3.length];
  int elementOfUnion = 0;
      
  for (int i = 0; i< array1.length; i++){
     unionArray[i] = array1[i];
     elementOfUnion = i + 1 ;
  }
  int index = 0;
  for (int i = elementOfUnion; i < unionArray.length; i++){
     unionArray[i] = array3[index];
     index++;
  }
  
  
  return unionArray;
}


public boolean isSet(int[] array){
  boolean duplicates = true;
  
  for (int i = 0; i < array.length; i++){
     for(int n = i+1; n < array.length; n++){
        if (array[i] == array[n])
           duplicates = false;
     }
  }
     
  return duplicates;
}

What I was trying to do is to use all of array1 elements in the unionArray, check if array2 has any duplicates with array1, and then move all the non-duplicate elements from array2 to a new array3, and concatenate array3 to unionArray.

like image 416
Laith.jas Avatar asked Nov 28 '20 20:11

Laith.jas


2 Answers

It will be much easier to do it with Collection API or Stream API. However, you have mentioned that you want to do it purely using arrays and without importing any class, it will require a few lengthy (although simple) processing units. The most important theories that drive the logic is how (given below) a union is calculated:

n(A U B) = n(A) + n(B) - n(A ∩ B)

and

n(Only A) = n(A) - n(A ∩ B)
n(Only B) = n(B) - n(A ∩ B)

A high-level summary of this solution is depicted with the following diagram:

enter image description here

Rest of the logic has been very clearly mentioned through comments in the code itself.

public class Main {
    public static void main(String[] args) {
        // Test
        display(union(new int[] { 1, 2, 3, 4 }, new int[] { 3, 4, 5, 6 }));
        display(union(new int[] { 1, 2, 3 }, new int[] { 4, 5, 6 }));
        display(union(new int[] { 1, 2, 3, 4 }, new int[] { 1, 2, 3, 4 }));
        display(union(new int[] { 1, 2, 3, 4 }, new int[] { 3, 4 }));
        display(union(new int[] { 1, 2, 3, 4 }, new int[] { 4, 5 }));
        display(union(new int[] { 1, 2, 3, 4, 5, 6 }, new int[] { 7, 8 }));
    }

    public static int[] union(int[] array1, int[] array2) {
        // Create an array of the length equal to that of the smaller of the two array
        // parameters
        int[] intersection = new int[array1.length <= array2.length ? array1.length : array2.length];
        int count = 0;

        // Put the duplicate elements into intersection[]
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array2.length; j++) {
                if (array1[i] == array2[j]) {
                    intersection[count++] = array1[i];
                }
            }
        }

        // Create int []union of the length as per the n(A U B) = n(A) + n(B) - n(A ∩ B)
        int[] union = new int[array1.length + array2.length - count];

        // Copy array1[] minus intersection[] into union[]
        int lastIndex = copySourceOnly(array1, intersection, union, count, 0);

        // Copy array2[] minus intersection[] into union[]
        lastIndex = copySourceOnly(array2, intersection, union, count, lastIndex);

        // Copy intersection[] into union[]
        for (int i = 0; i < count; i++) {
            union[lastIndex + i] = intersection[i];
        }

        return union;
    }

    static int copySourceOnly(int[] source, int[] exclude, int[] target, int count, int startWith) {
        int j, lastIndex = startWith;
        for (int i = 0; i < source.length; i++) {
            // Check if source[i] is present in intersection[]
            for (j = 0; j < count; j++) {
                if (source[i] == exclude[j]) {
                    break;
                }
            }

            // If j has reached count, it means `break;` was not executed i.e. source[i] is
            // not present in intersection[]
            if (j == count) {
                target[lastIndex++] = source[i];

            }
        }
        return lastIndex;
    }

    static void display(int arr[]) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(i < arr.length - 1 ? arr[i] + ", " : arr[i]);
        }
        System.out.println("]");
    }
}

Output:

[1, 2, 5, 6, 3, 4]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4]
[1, 2, 3, 4]
[1, 2, 3, 5, 4]
[1, 2, 3, 4, 5, 6, 7, 8]
like image 75
Arvind Kumar Avinash Avatar answered Oct 03 '22 06:10

Arvind Kumar Avinash


Using Java's streams could make this quite simpler:

public int[] union(int[] array1, int[] array2) {
    return Stream.of(array1, array2).flatMapToInt(Arrays::stream).distinct().toArray();
}
like image 21
Mureinik Avatar answered Oct 03 '22 06:10

Mureinik