Java array replacements

Hello I have 3 integer arrays.

• array #1 has information and contains duplicates.
• array #2 contains values that might be in array 1.
• array #3 has replacement values.
• array #2 and array #3 are the same size and do not contain duplicates.

I want to check if an element from array #2 is in array #1.
If the element is in array #1 I want it replaced with an element from array #3.
The element from #3 that replaces the original needs to have the same location in the array as #2.
A way I could do it is:

for (int i = 0; i<arr1.length; i++){
  for (int a = 0; a<arr2.length; a++){
    if(arr1[i]==arr2[a]){
      arr1[i]=arr3[a];
      break;
    }
  }
}

What I am wondering is if there is a quicker or better way to do this.

The current algorithm has time complexity O(n * m) with n = length of array #1 and m = length of array #2.

There is an algorithm that has a better time complexity.

Sketch of algorithm:

1. Sort array #1, keep track of how elements move to reverse sorting at the end (O(n log(n)))
2. Sort array #2, permutate elements in array #3 accordingly (O(m log(m)))
3. Find all elements in array #1, that are also in array #2 and replace them with the elements at same position in array #3 (O(n + m))
4. Un-Sort array #1 utilizing the tracking from 1. (O(n))

In total, we get O(n log(n) + m log(m) + n + m + n) ∈
O(n log(n) + m log(m))

If arrays #2 and #3 must be un-shuffled aswell, one can either copy those arrays or keep track during sorting aswell and un-shuffle them aswell since un-shuffling takes "only" O(m).

Use a Set of the elements in array1 to determine if an element is in it.
Loop over array2 and copy over forom array3 if the set contains its element:

Set<T> set = Arrays.stream(arr1).collect(toSet()); // O(n)
for (int i = 0; i < arr2.length; i++){         // O(m)
    if (set.contains(arr2[i])) {
      arr2[i] = arr3[i];
    }
}

Given array1 is size n and array2 is size m...
All operations on a Set are constant time (ie O(1)), so building the set cost O(n).
Looping over array2 is O(m) - the set lookup cost is O(1)

Overall cost O(n + m) - ie "linear".

Your current cost is O(n * m) - ie "quadratic".

Note: You have not specified the type of the arrays. If they are primitive (eg int), building the set needs the minor enhancement of adding a call to boxed(), because java does not support collections of primitives:

Arrays.stream(arr1).boxed().collect(toSet())

Array #2 and Array #3 are a bad replacement for a HashMap.

Map<T, T> replacements = new HashMap<>();
for (int i = 0; i < arr2.length; i++) {
  replacements.put(arr2[i], arr3[i]);
}
for (int i = 0; i < arr1.length; i++) {
  if (replacements.containsKey(arr1[i]) {
    arr1[i] = replacements.get(arr1[i]);
  }
}

This will have approximately O(n) time complexity.