To begin, I am doing this using solely arrays - meaning no hash maps or array lists. It is in Java.

I am trying to create a method, project, which takes in two integer arrays (of different sizes).

I am trying to compare them in a way to get the following output: Projecting [1, 3, 5, 3] to [2, 1, 6, 3, 1, 4, 5, 3] results in: [1, 3, 1, 5, 3]. However, Projecting [2, 1, 6, 3, 1, 4, 5, 3] to [1, 3, 5, 3] results in: [1, 3, 5, 3].

I believe the nested for loop might be wrong as it is iterating through the first indices for the first array all the way through the second array, then going to the next.

I'm getting an ArrayIndexOutOfBoundsException for the line that is starred (tempArray[i] == arr1[i], I know it shouldn't be tempArray[i] but not sure what exactly to put. I'm not sure how to compare them in a way to produce the line above, as it needs to be in order. What would be the best way to accomplish this or correct the code?

I attempted the following code:

public int[] project(int[] arr1, int[] arr2) {
    int counter = 0;
    for(int i=0 ; i < arr1.length; i  ) {
        for (int j=0; j < arr2.length; j  ) {
            if(arr1[i] == arr2[j]) {
                counter  ;
            }
        }
    }
    
    int[] tempArray = new int[counter];
    
    for(int i=0 ; i < arr1.length; i  ) {
        for (int j=0; j < arr2.length; j  ) {
            if(arr1[i] == arr2[j]) {
                
                **tempArray[i] = arr1[i];**    
                
            }
        }
    }

Edit: The ArrayIndexOutOfBounds error is gone, but now my return statement is: Projecting [1, 3, 5] to [2, 1, 6, 3, 1, 4, 5, 3] results in: [1, 3, 5, 0, 0], when it needs to be Projecting [1, 3, 5] to [2, 1, 6, 3, 1, 4, 5, 3] results in: [1, 3, 1, 5, 3]. Any idea what is causing this issue?

CodePudding user response：

I think you have a typo in your first for loop

change this to later

arr1[i] == arr2[i]

to

arr1[i] == arr2[j]

Regarding overlapping issues in the projection array, you need to maintain different value as your index rather than i or j which is used by arr1 and arr2 respectively

int[] tempArray = new int[counter];
int index = 0;

for(int i=0 ; i < arr1.length; i  ) {
    for (int j=0; j < arr2.length; j  ) {
        if(arr1[i] == arr2[j]) {
            tempArray[index  ] = arr1[i];
        }
    }
}

For the values which you are expecting you should loop through arr2 first

for(int j=0 ; j < arr2.length; j  ) {
    for (int i=0; i < arr1.length; i  ) {
        if(arr1[i] == arr2[j]) {
            tempArray[index  ] = arr1[i];
        }
    }
}

If the contents of array are not hardcoded and you dont know the order in which you want to pass, you can make use of length

  int[] ans;
  if(a.length < b.length) {
      ans = project(a, b);
  } else {
      ans = project(b, a);
  }

Output:

[1, 3, 1, 5, 3]

CodePudding user response：

You currently have index variables (i, j) tracking the indexes of each input array as you loop through them, but you also need to keep track of the write head of the result array. Initialize, say int k = 0 before the outer for loop, then set the value like this: tempArray[k ] = array1[i];.

You can forgo the first loop If you are OK with performing a single array copy. Initialize an array as long as the second input array (since there can never be more duplicated elements than existing elements) as the tempArray. Then if you want it to fit exactly, initialize the final array to the exact length k and use System#arrayCopy.

CodePudding user response：

this will probably solve your problem

public int[] project(int[] arr1, int[] arr2) {
    int counter = 0;
    for (int i : arr2) {
        if (Arrays.binarySearch(arr1, i) >= 0) {
            counter  ;
        }
    }
    int[] arr4 = new int[counter];
    int index = 0;
    for (int i : arr2) {
        if (Arrays.binarySearch(arr1, i) >= 0) {
            arr4[index  ] = i;
        }
    }

    return arr4;
}

CodePudding user response：

For your second problem, I think, in your temporary array, you should be saving the values from arr2[j] instead of arr1[i]

Also, you need a different counter (set to 0 initially and incremented in the loop) for setting the values in tempArray[counter]

What I mean exactly is

int counter = 0;
for(int i=0 ; i < arr1.length; i  ) {
    for (int j=0; j < arr2.length; j  ) {
        if(arr1[i] == arr2[j]) {
            tempArray[counter] = arr2[j];
            counter  ;           
        }
    }
}

CodePudding user response：

The nested iteration is expensive, so we want to avoid that. The first thing to do is sort the array we are projecting from so we can perform a binary search on it. Second, don't execute the nested iteration to determine the output array size. Create an array the size of the array we are projecting to since it can be no longer than that.

public int[] projection(int[] a, int[] b) {
  int[] temp = new int[b.length];
  int nextIndex = 0;
  for (int x : b) {
    if (contains(a, x)) {
      temp[nextIndex  ] = x;
    }
  }
  return slice(temp, nextIndex);
}

private boolean contains(int[] array, int value) {
  for (int element : array) {
    if (element == value) {
      return true;
    }
  }
  return false;
}

private int[] slice(int[] src, int size) {
  int[] slice = new int[size];
  for (int index = 0 ; index < size ;   index) {
    slice[index] = src[index];
  }
  return slice;
}