当前位置: 首页 > 面试题库 >

在java 中的Array 中找到总和最接近X 的对。

白青青
2023-03-14
问题内容

给定一个已排序的数组,我们需要在 Array 中找到一个总和接近于数字 X 的对。
例如:

array[]={-40,-5,1,3,6,7,8,20};
The pair whose sum is closest to 5 :  1 and 3

问题答案:

解决方案1:
您可以检查每对数字并找到接近 X 的总和。
Java 代码:

public static void findPairWithClosestToXBruteForce(int arr[],int X)
{
    if(arr.length<2)
        return;
    // Suppose 1st two element has minimum diff with X
    int minimumDiff=Math.abs(arr[0]+arr[1]-X);
    int pair1stIndex=0;
    int pair2ndIndex=1;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i+1; j < arr.length; j++) {
            int tempDiff=Math.abs(arr[i]+arr[j]-X);

            if(tempDiff< minimumDiff)
            {
                pair1stIndex=i;
                pair2ndIndex=j;
                minimumDiff=tempDiff;
            }
        }
    }
    System.out.println(" The pair whose sum is closest to X using brute force method: "+arr[pair1stIndex]+" "+ arr[pair2ndIndex]);
}

解决方案2:
我们将维护两个索引,一个在开头(l=0),一个在结尾(r=n-1) * 迭代直到 l < r * 将差异计算为 arr[l] + arr[r]-x * 如果 abs (diff) < minDiff 然后更新最小总和和对。 * 如果 arr[l] + arr[r] 小于 X,这意味着如果我们想找到接近 X 的和,做 r– * 如果 arr[l] + arr[r] 大于 0,这意味着如果我们想找到接近 X 的总和,请执行 l++
java代码:

public static void findPairWithClosestToX(int arr[],int X) {

    int minimumDiff = Integer.MAX_VALUE;
    int n=arr.length;
    if(n<0)
        return;
    // left and right index variables
    int l = 0, r = n-1;

    // variable to keep track of the left and right pair for minimumSum
    int minLeft = l, minRight = n-1;

    while(l < r)
    {

        int currentDiff= Math.abs(arr[l] + arr[r]-X);
        /*If abs(diff) is less than min dif, we need to update sum and pair */
        if(currentDiff < minimumDiff)
        {
            minimumDiff = currentDiff;
            minLeft = l;
            minRight = r;
        }
        if(arr[l] + arr[r] < X)
            l++;
        else
            r--;
    }

    System.out.println(" The pair whose sum is closest to X : "+arr[minLeft]+" "+ arr[minRight]);
}

时间复杂度:O(NLogN)

寻找总和最接近 X 的对的 Java 程序:

package org.arpit.java2blog;

public class FindPairClosestToXMain {

    public static void main(String[] args)
    {
        int array[]={-40,-5,1,3,6,7,8,20};
        findPairWithClosestToXBruteForce(array,5);
        findPairWithClosestToX(array,5);
    }
    public static void  findPairWithClosestToXBruteForce(int arr[],int X)
    {
        if(arr.length<2)
            return;
        // Suppose 1st two element has minimum diff with X
        int minimumDiff=Math.abs(arr[0]+arr[1]-X);
        int pair1stIndex=0;
        int pair2ndIndex=1;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                int tempDiff=Math.abs(arr[i]+arr[j]-X);

                if(tempDiff< minimumDiff)
                {
                    pair1stIndex=i;
                    pair2ndIndex=j;
                    minimumDiff=tempDiff;
                }
            }
        }
        System.out.println(" The pair whose sum is closest to X using brute force method: "+arr[pair1stIndex]+" "+ arr[pair2ndIndex]);
    }

    public static void findPairWithClosestToX(int arr[],int X) {

        int minimumDiff = Integer.MAX_VALUE;
        int n=arr.length;
        if(n<0)
            return;
        // left and right index variables
        int l = 0, r = n-1;

        // variable to keep track of the left and right pair for minimumSum
        int minLeft = l, minRight = n-1;

        while(l < r)
        {

            int currentDiff= Math.abs(arr[l] + arr[r]-X);
            /*If abs(diff) is less than min dif, we need to update sum and pair */
            if(currentDiff < minimumDiff)
            {
                minimumDiff = currentDiff;
                minLeft = l;
                minRight = r;
            }
            if(arr[l] + arr[r] < X)
                l++;
            else
                r--;
        }

        System.out.println(" The pair whose sum is closest to X : "+arr[minLeft]+" "+ arr[minRight]);
    }
}

当你运行上面的程序时,你会得到以下输出:

   The pair whose sum is closest to X using brute force method: 1 3
The pair whose sum is closest to X : 1 3


 类似资料:
  • 问题内容: 问题 : 给定 +ve 和 -ve 整数数组,我们需要在数组中找到总和接近零的一对。 例如: 问题答案: 您可以检查每一对数字并找到最小和。 java代码: 解决方案2: 对数组进行排序。 * 我们将维护两个索引,一个在开头(l=0),一个在结尾(r=n-1) 迭代直到 l < r * 计算 arr[l] + arr[r] 的总和 * 如果 abs (sum) < abs (minSu

  • 问题内容: 我想知道是否有可能找到一个最接近的元素的元素 ,是不是 在那里。 例如,如果我们具有[1,3,6,7]值,并且正在寻找最接近4的元素,则它应返回3,因为3是数组中的最大数字,小于4。 我希望这是有道理的,因为英语不是我的母语。 问题答案: 如果数组已排序,则可以在以下位置进行修改的二进制搜索:

  • 问题内容: 我想在哈希图中搜索键,然后找到与该键最接近的键! 因此,基本上我想搜索一个long,如果地图中不存在该long,则找到与该long值最接近的匹配项!我怎样才能做到这一点!? 提前感谢 问题答案: 如果不迭代其所有键,就无法做到这一点。我假设这不是您想要的,所以这是一种使用的方法:

  • 问题内容: 我有一个由我从Google Maps Directions服务获得的latlng绘制的多义线。现在,我想在折线上找到最接近给定点的点。 (对我而言)最明显的方法是通过折线上的所有点进行循环并找到它们与给定点之间的距离,但是这种方法效率不高,因为折线上的点可能很大。 我很高兴听到这样做的其他选择。提前致谢。 问题答案: 它正在找到直线上最接近鼠标的点。另请注意,这是一个Google Ma

  • 问题内容: 我向我的脚本发送这些参数:纬度:41.0186经度:28.964701(为示例)。我想找到最近的位置的名字。这该怎么做?(查询的代码必须更改的地方) SQL查询: 位置表是这样的:(实际上,这是巨大的表) 问题答案: 使用这个功能 您可以通过此功能进行排序,但是在大型数据集上这将非常慢,因此请尝试对记录集进行预过滤 UPD: 使用@chopikadze的测试数据: 假设地球不是大地水准