您的位置: 首页  >  IT文章  >  给定两个有序数组跟一个指定的sum值，从两个数组中各找一个数使得这两个数的和与指定的sum值相差最小

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

分类: IT文章 • 2024-01-14 14:41:01
给定两个有序数组和一个指定的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/

相关推荐