Geek asks and answers

The closest pair sum in two sorted arrays

For two sorted arrays of integers aand band an integer, cI need to find i,jthat:

a[i] + b[j] <= c

and a[i] + b[j]are as large as possible.

The best solution I can think of is in O ( n log n ) time, taking every integer from the first array and finding the lower bound " c-a[i]".
Can someone suggest me a better way to do this (maybe in O ( n ))?

+5
source share
3 answers

, :
" b- []?"

+6

, b [] ....... u b u, .... []. ... "c", .

+2

Below, the solution is in linear time complexity O (n), spatial complexity O (1)

public class ClosestPair {

    public static void main(String[] args)
    {
        int ar2[] = {4, 5, 7};
        int ar1[] = {10, 20, 30, 40};
        int x = 10 ;
        closest(ar1,ar2,x);
    }
    public static void closest(int[] ar1, int[] ar2, int x)
    {   int diff=Integer.MAX_VALUE;
        int first_num=0;
        int second_num=0;
        int second_diff=Integer.MAX_VALUE;
        for(int i=0; i<ar1.length; i++)
        {
            if(x==ar1[i] )
            {
                System.out.println("no pair possible");
                return;
            }
        }
        for(int i=0; i<ar2.length; i++)
        {
            if(x==ar2[i])
            {
                System.out.println("no pair possible");
                return;
            }
        }
        for(int i=0; i<ar2.length; i++)
        {

            if(Math.abs(x-ar2[i])<=diff)
            {
                diff=Math.abs(x-ar2[i]);
                first_num=ar2[i];
            }
        }
       diff=x-first_num;
       for(int i=0; i<ar1.length; i++)
       {
           if(Math.abs(diff-ar1[i])<=second_diff)
           {
               second_diff= Math.abs(diff-ar1[i]);
               second_num= ar1[i];
           }
       }
       System.out.println(first_num + " "+ second_num);
    }
}
0
source

More articles:


All Articles