c - 2 つの並べ替えられた配列の最も近いペアの和

Question

整数の 2 つの並べ替えられた配列aとb、および整数 が与えられた場合c、次のように見つける必要がありますi,j。

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

そしてa[i] + b[j]できるだけ大きい。

私が考えることができる最善の解決策は、O ( n log n ) 時間で、最初の配列からすべての整数を取得し、 " " の下限を見つけることc-a[i]です。
誰かがこれを行うためのより良い方法を提案できますか (おそらく O( n ) 時間で)?

Answer 1

それについて少し考えてみると、
「毎回、ソートされたb配列でa []からの連続する値を検索する必要がありますか？」と自問することができます。

Answer 2

次回は配列b []全体を検索する必要はないと思います.......配列bの開始とこれまでに見つかった下限の間を検索する必要があります....aの次の要素を検索する[].それは間違いなく時間の複雑さを軽減します...そして、指定されたターゲット「c」を見つけたら、検索を停止する必要があります。

Answer 3

以下のソリューションは、線形の時間複雑度 O(n)、空間複雑度 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);
    }
}