给定两个有序数组和一个指定的sum值，从两个数组中各找一个数使得这两个数的和与指定的sum值相差最小
浏览数：12 /
时间：2015年06月08日
?
题目：给定两个有序数组和一个指定的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/
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
