给定两个有序数组和一个指定的sum值，从两个数组中各找一个数使得这两个数的和与指定的sum值相差最小

 

题目：给定两个有序数组和一个指定的sum值，从两个数组中各找一个数使得这两个数的和与指定的sum值相差最小。

比如，有两个有序数组，数组1 为{ -5, -1, 0, 1, 4, 5, 7, 9 }，数组2 为{ -3, 3, 10, 12, 15, 18, 21, 28 }，如果 sum 为20，

则获得的结果为[-1 , 21]，如sum为30，则与sum相差最小的两个数为[7 , 28] 。

解决该题目的方法可以采用如下的步骤：

1. 定义两个索引变量,  leftIndex为数组1的索引值，初始值为0，rightIndex为数组2的索引，初始值为数组2的长度减一。定义一个差值diff，初始值为 Integer.MAX_VALUE

2.  while (leftIndex < lenOne && rightIndex >= 0)  则执行相关的逻辑，此处分三种情况

•      if (Math.abs(arrayOne[leftIndex] + arrayTwo[rightIndex]- expectedSum) < diff)  则更新diff和数组一和数组二中期望的两个数的值
•      else if (arrayOne[leftIndex] + arrayTwo[rightIndex] < expectedSum)  则数组一的leftIndex++
•      else 其它情况下，数组二的下标rightIndex–

3.  while循环结束，输出期望的值。

有了这个思想，我们可以编写如下的程序了。

帮助

public class FindClosestPairExample {

 

    public static void findAndPrintClosest(int[] arrayOne, int[] arrayTwo,

            int expectedSum) {

        int lenOne = arrayOne.length;

        int lenTwo = arrayTwo.length;

        int diff = Integer.MAX_VALUE;

        int resultOne = 0;

        int resultTwo = 0;

        int leftIndex = 0;

        int rightIndex = lenTwo - 1;

 

        while (leftIndex < lenOne && rightIndex >= 0) {

            if (Math.abs(arrayOne[leftIndex] + arrayTwo[rightIndex]

                    - expectedSum) < diff) {

                resultOne = arrayOne[leftIndex];

                resultTwo = arrayTwo[rightIndex];

                diff = Math.abs(resultOne + resultTwo - expectedSum);

            } else if (arrayOne[leftIndex] + arrayTwo[rightIndex] < expectedSum) {

                leftIndex++;

            } else {

                rightIndex--;

            }

        }

 

        System.out.printf("[%d , %d] \n", resultOne, resultTwo);

    }

 

}

测试代码如下：

帮助

public static void main(String[] args) {

        int[] arrayOne = { -5, -1, 0, 1, 4, 5, 7, 9 };

        int[] arrayTwo = { -3, 3, 10, 12, 15, 18, 21, 28 };

        System.out.println("两个有序数组的内容为:");

        System.out.println("数组一：" + Arrays.toString(arrayOne));

        System.out.println("数组二：" + Arrays.toString(arrayTwo));

 

        System.out.println("与期望值20相差最小的两个数为:");

        findAndPrintClosest(arrayOne, arrayTwo, 20);

        System.out.println("与期望值35相差最小的两个数为:");

        findAndPrintClosest(arrayOne, arrayTwo, 35);

 

    }

程序运行结果：

两个有序数组的内容为:
数组一：[-5, -1, 0, 1, 4, 5, 7, 9]
数组二：[-3, 3, 10, 12, 15, 18, 21, 28]
与期望值20相差最小的两个数为:
[-1 , 21] 
与期望值35相差最小的两个数为:
[7 , 28] 

原文地址http://thecodesample.com/?p=855

 

更多例子请访问 http://thecodesample.com/