题目:给定两个有序数组和一个指定的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/
相关推荐
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 9、回文数:(IsPalindrome) 判断一个整数是否是回文数。 14、最长公共前缀:...
leetcode 答案 每个文件都用C语言实现了一个LeetCode上的算法题,序号就是题号,都是可以编译跑通的(C语言基础不好,有些内容...请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 26.re
文章目录两数之和两数相加无重复字符串的最长子串寻找两个有序数组的中位数 两数之和 给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。 你可以假设每种...
两个有序数组中,寻找中值。复杂度O(log(n+m))。加入要查找第k小,每次在两个数组中,比较中值的大小,进而缩小范围。 *+ 含有.*的正则匹配判断。 dp[i][j]表示前i个正则串匹配前j个字符。如果是. or a的话,直接...
6.数据结构中评价算法的两个重要指标是(时间复杂度和空间复杂度) 【北京理工大学 2001 七、1(2分)】 7. 数据结构是研讨数据的_(1)物理结构_和_(2)逻辑结构 _,以及它们之间的相互关系,并对与这种结构定义...
e. 如有可能,请建立一个存储商品名称和数量的文本文件,并为二叉搜索树建立一个成员函数SetupInventory(),用于从该文本文件中读取库存商品的数据, 实验报告要求: 1、 按要求记录下二叉搜索树的完整实验...
arr,和一个整数aim,返回哪两个位置的数可以加出 aim 。假设一组数只有一组答案 algorithm.TowSum 给定一个链表 list。 如果: list = 1 调整后为 1 list = 1->2 调整为 1 -> 2 list = 1->2->3 调整为 1 -> 2 -> 3 ...
Q0049 一个有序数组和一个无序数组,从无序数组中取出每条记录与有序数组比较,如果符合条件,把无序数组中的值加入到有序数组中,问这是什么排序? 插入排序法 Q0050 程序与进程的区别? 程序是为了完成某种任务...
(二叉搜索树的一个特性:通过中序遍历所得到的序列,就是有序的。) 后:左右根 快速排序就是个二叉树的前序遍历,归并排序就是个二叉树的后续遍历 二叉树的问题难点在于,如何把题目的要求细化成每个节点需要做的...
用三目条件运算符,求变量 x 、y的最大值和最小值,并分别赋给变量 max 和min, 这两个赋值语句分别是 _________和________。 3.结构化程序设计的三种基本流程控制结构是:_____________、 _____________、__________...