c - 两个排序数组中最接近的对总和

Question

给定两个排序的整数数组，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);
    }
}