Given two arrays that have only positive values. It is necessary to return the minimum value that is in both arrays. For example:

А{3,2,5,6,4} B{9,7,2,3,1,5}

That is, in this example, the minimum value will be 2.

I wrote this code here:

 public static int solution(int[] A, int[] B) { int min = A[0]; for(int i=1; i<A.length; i++) { if(min > A[i]) { min = A[i]; } } for(int j=0; j<B.length; j++) { if(min == B[j]) { System.out.println(min); } } System.out.println(min); return min; }

I know that it does not work as it should, but I do not know how to finish it. May need recursion?

  • find the intersection of two arrays and take a minimum - splash58
  • That is, to find the value that is present in one and the other array, and then what? Run for each one and ask if this is the minimum value? - tarasula
  • one
    sort by. or sort at once, then use two pointers to go through both arrays before scrolling the values - splash58

3 answers 3

For a change, here is Java-8. The simplest solution is O(A.length*B.length)

 public static OptionalInt solution(int[] A, int[] B) { return IntStream.of(A).filter(x -> IntStream.of(B).anyMatch(y -> x == y)).min(); }

Here we create a stream of elements of one array and filter by elements of another array. If there are no matching elements (or one of the arrays is empty), we get an empty OptionalInt as a result.

If the arrays are large, you can sort one of the arrays and use the binary search:

 public static OptionalInt solution(int[] A, int[] B) { int[] sortedB = B.clone(); // менять аргумент некрасиво, делаем копию Arrays.sort(sortedB); return IntStream.of(A).filter(x -> Arrays.binarySearch(sortedB, x) >= 0).min(); }

Here the amortized complexity will be O((A.length+B.length)*log(B.length)) .

Examples:

 System.out.println(solution(new int[] {3,2,5,6,4}, new int[] {9,7,2,3,1,5})); System.out.println(solution(new int[] {10,12,15,6,4}, new int[] {9,7,2,3,1,5}));

Conclusion:

 OptionalInt[2] OptionalInt.empty
  • Super. Can you advise something to read about the complexity? I often come across this, but I can’t understand how to calculate it or write something with a certain complexity. - tarasula
  • one
    @tarasula, do not even know what to read. Well, if you loop through A , and inside another loop through B , then it is clear that the complexity will be O(A.length*B.length) . The complexity of the binary search is also known - the logarithm of the number of elements. The amortized sorting complexity of TimSort / QuickSort - O(n*log(n)) (in the worst case O(n^2) ) - this can be seen in the description of these algorithms in wikipedia, for example. - Tagir Valeev

It is possible not to sort two arrays, but to sort only the first one and look for matches in the second array. First, we take the minimum in the first array, then we go through the second array and look for a match. Then, if you have not found anything, we take the second minimum from the first array and again pass through the second one. We continue until we find a match.

 import java.util.Arrays; public class SOMain { public static void main(String[] args) { int[] A = {3, 2, 5, 6, 4}; int[] B = {9, 7, 2, 3, 1, 5}; Arrays.sort(A); for (int first : A) { for (int second : B) { if (first == second) { System.out.println(first); return; } } } throw new RuntimeException("Совпадений не найдено"); } }

For comparison, I will give an option with sorting both arrays and two iterators:

 import java.util.Arrays; public class SOMain { public static void main(String[] args) { int[] A = {3, 2, 5, 6, 4}; int[] B = {9, 7, 2, 3, 1, 5}; Arrays.sort(A); Arrays.sort(B); int i1 = 0; int i2 = 0; while (i1 < A.length && i2 < B.length) { int cmp = Integer.compare(A[i1], B[i2]); switch (cmp) { case 1: // Если число из первого массива больше, i2++; // двигаем итератор второго массива break; case -1: // Если число из второго массива больше, i1++; // двигаем итератор первого массива break; case 0: // Если числа совпадают, выводим результат System.out.println(A[i1]); return; } } throw new RuntimeException("Совпадений не найдено"); } }
  • Understood, thanks! - tarasula
 public static int solution(int[] A, int[] B) { int min = A[0]; for(int i=1; i<A.length; i++) { if(min > A[i]) { min = A[i]; } } for(int j=0; j<B.length; j++) { if(min > B[j]) { min = B[j]; } } System.out.println(min); return min; }