给定两个排序数组和一个数字x，找出其和最接近x的一对 这对数组的每个数组中都有一个元素 . 给定两个数组ar1[0…m-1]和ar2[0…n-1]以及一个数字x，我们需要找到对ar1[i]+ar2[j]，这样（ar1[i]+ar2[j]-x）的绝对值最小。 例子：
null
Input: ar1[] = {1, 4, 5, 7}; ar2[] = {10, 20, 30, 40}; x = 32 Output: 1 and 30Input: ar1[] = {1, 4, 5, 7}; ar2[] = {10, 20, 30, 40}; x = 50 Output: 7 and 40
我们强烈建议您尽量减少浏览器数量，并首先自己尝试。 A. 简单解决方案 就是运行两个循环。外循环考虑第一个数组中的每个元素，内循环检查第二个数组中的元素对。我们跟踪ar1[i]+ar2[j]和x之间的最小差异。 我们能做到 在O（n）时间内 使用以下步骤。 1） 使用以下命令将给定的两个数组合并为大小为m+n的辅助数组 合并排序的合并过程 。合并时，保留另一个大小为m+n的布尔数组，以指示合并数组中的当前元素是来自ar1[]还是ar2[]。 2）考虑合并数组并使用 求和最接近x的对的线性时间算法 一个额外的事情，我们只需要考虑那些有一个元素从AR1 []和其他从AR2]，我们使用布尔数组为此目的。 我们能在一次传球和额外的空间内完成吗？ 其思想是从一个数组的左侧和另一个数组的右侧开始，并使用与上述方法的步骤2相同的算法。下面是详细的算法。
1) Initialize a variable diff as infinite (Diff is used to store the difference between pair and x). We need to find the minimum diff.2) Initialize two index variables l and r in the given sorted array. (a) Initialize first to the leftmost index in ar1: l = 0 (b) Initialize second the rightmost index in ar2: r = n-13) Loop while l = 0 (a) If abs(ar1[l] + ar2[r] - sum) < diff then update diff and result (b) If (ar1[l] + ar2[r] < sum ) then l++ (c) Else r-- 4) Print the result.
下面是这种方法的实现。
C++
// C++ program to find the pair from two sorted arrays such // that the sum of pair is closest to a given number x #include <iostream> #include <climits> #include <cstdlib> using namespace std; // ar1[0..m-1] and ar2[0..n-1] are two given sorted arrays // and x is given number. This function prints the pair from // both arrays such that the sum of the pair is closest to x. void printClosest( int ar1[], int ar2[], int m, int n, int x) { // Initialize the diff between pair sum and x. int diff = INT_MAX; // res_l and res_r are result indexes from ar1[] and ar2[] // respectively int res_l, res_r; // Start from left side of ar1[] and right side of ar2[] int l = 0, r = n-1; while (l<m && r>=0) { // If this pair is closer to x than the previously // found closest, then update res_l, res_r and diff if ( abs (ar1[l] + ar2[r] - x) < diff) { res_l = l; res_r = r; diff = abs (ar1[l] + ar2[r] - x); } // If sum of this pair is more than x, move to smaller // side if (ar1[l] + ar2[r] > x) r--; else // move to the greater side l++; } // Print the result cout << "The closest pair is [" << ar1[res_l] << ", " << ar2[res_r] << "] " ; } // Driver program to test above functions int main() { int ar1[] = {1, 4, 5, 7}; int ar2[] = {10, 20, 30, 40}; int m = sizeof (ar1)/ sizeof (ar1[0]); int n = sizeof (ar2)/ sizeof (ar2[0]); int x = 38; printClosest(ar1, ar2, m, n, x); return 0; } |
JAVA
// Java program to find closest pair in an array class ClosestPair { // ar1[0..m-1] and ar2[0..n-1] are two given sorted // arrays/ and x is given number. This function prints // the pair from both arrays such that the sum of the // pair is closest to x. void printClosest( int ar1[], int ar2[], int m, int n, int x) { // Initialize the diff between pair sum and x. int diff = Integer.MAX_VALUE; // res_l and res_r are result indexes from ar1[] and ar2[] // respectively int res_l = 0 , res_r = 0 ; // Start from left side of ar1[] and right side of ar2[] int l = 0 , r = n- 1 ; while (l<m && r>= 0 ) { // If this pair is closer to x than the previously // found closest, then update res_l, res_r and diff if (Math.abs(ar1[l] + ar2[r] - x) < diff) { res_l = l; res_r = r; diff = Math.abs(ar1[l] + ar2[r] - x); } // If sum of this pair is more than x, move to smaller // side if (ar1[l] + ar2[r] > x) r--; else // move to the greater side l++; } // Print the result System.out.print( "The closest pair is [" + ar1[res_l] + ", " + ar2[res_r] + "]" ); } // Driver program to test above functions public static void main(String args[]) { ClosestPair ob = new ClosestPair(); int ar1[] = { 1 , 4 , 5 , 7 }; int ar2[] = { 10 , 20 , 30 , 40 }; int m = ar1.length; int n = ar2.length; int x = 38 ; ob.printClosest(ar1, ar2, m, n, x); } } /*This code is contributed by Rajat Mishra */ |
Python3
# Python3 program to find the pair from # two sorted arrays such that the sum # of pair is closest to a given number x import sys # ar1[0..m-1] and ar2[0..n-1] are two # given sorted arrays and x is given # number. This function prints the pair # from both arrays such that the sum # of the pair is closest to x. def printClosest(ar1, ar2, m, n, x): # Initialize the diff between # pair sum and x. diff = sys.maxsize # res_l and res_r are result # indexes from ar1[] and ar2[] # respectively. Start from left # side of ar1[] and right side of ar2[] l = 0 r = n - 1 while (l < m and r > = 0 ): # If this pair is closer to x than # the previously found closest, # then update res_l, res_r and diff if abs (ar1[l] + ar2[r] - x) < diff: res_l = l res_r = r diff = abs (ar1[l] + ar2[r] - x) # If sum of this pair is more than x, # move to smaller side if ar1[l] + ar2[r] > x: r = r - 1 else : # move to the greater side l = l + 1 # Print the result print ( "The closest pair is [" , ar1[res_l], "," ,ar2[res_r], "]" ) # Driver program to test above functions ar1 = [ 1 , 4 , 5 , 7 ] ar2 = [ 10 , 20 , 30 , 40 ] m = len (ar1) n = len (ar2) x = 38 printClosest(ar1, ar2, m, n, x) # This code is contributed by Smitha Dinesh Semwal |
C#
// C# program to find closest pair in // an array using System; class GFG { // ar1[0..m-1] and ar2[0..n-1] are two // given sorted arrays/ and x is given // number. This function prints the // pair from both arrays such that the // sum of the pair is closest to x. static void printClosest( int []ar1, int []ar2, int m, int n, int x) { // Initialize the diff between pair // sum and x. int diff = int .MaxValue; // res_l and res_r are result // indexes from ar1[] and ar2[] // respectively int res_l = 0, res_r = 0; // Start from left side of ar1[] // and right side of ar2[] int l = 0, r = n-1; while (l < m && r >= 0) { // If this pair is closer to // x than the previously // found closest, then update // res_l, res_r and diff if (Math.Abs(ar1[l] + ar2[r] - x) < diff) { res_l = l; res_r = r; diff = Math.Abs(ar1[l] + ar2[r] - x); } // If sum of this pair is more // than x, move to smaller // side if (ar1[l] + ar2[r] > x) r--; else // move to the greater side l++; } // Print the result Console.Write( "The closest pair is [" + ar1[res_l] + ", " + ar2[res_r] + "]" ); } // Driver program to test above functions public static void Main() { int []ar1 = {1, 4, 5, 7}; int []ar2 = {10, 20, 30, 40}; int m = ar1.Length; int n = ar2.Length; int x = 38; printClosest(ar1, ar2, m, n, x); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to find the pair // from two sorted arrays such // that the sum of pair is // closest to a given number x // ar1[0..m-1] and ar2[0..n-1] // are two given sorted arrays // and x is given number. This // function prints the pair from // both arrays such that the sum // of the pair is closest to x. function printClosest( $ar1 , $ar2 , $m , $n , $x ) { // Initialize the diff between // pair sum and x. $diff = PHP_INT_MAX; // res_l and res_r are result // indexes from ar1[] and ar2[] // respectively $res_l ; $res_r ; // Start from left side of // ar1[] and right side of ar2[] $l = 0; $r = $n - 1; while ( $l < $m and $r >= 0) { // If this pair is closer to // x than the previously // found closest, then // update res_l, res_r and // diff if ( abs ( $ar1 [ $l ] + $ar2 [ $r ] - $x ) < $diff ) { $res_l = $l ; $res_r = $r ; $diff = abs ( $ar1 [ $l ] + $ar2 [ $r ] - $x ); } // If sum of this pair is // more than x, move to smaller // side if ( $ar1 [ $l ] + $ar2 [ $r ] > $x ) $r --; // move to the greater side else $l ++; } // Print the result echo "The closest pair is [" , $ar1 [ $res_l ] , ", " , $ar2 [ $res_r ] , "] " ; } // Driver Code $ar1 = array (1, 4, 5, 7); $ar2 = array (10, 20, 30, 40); $m = count ( $ar1 ); $n = count ( $ar2 ); $x = 38; printClosest( $ar1 , $ar2 , $m , $n , $x ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to find // the pair from two sorted arrays such // that the sum of pair is closest // to a given number x // ar1[0..m-1] and ar2[0..n-1] are // two given sorted arrays // and x is given number. // This function prints the pair // from both arrays such that the // sum of the pair is closest to x. function printClosest( ar1, ar2, m, n, x) { // Initialize the diff // between pair sum and x. let diff = Number.MAX_VALUE; // res_l and res_r are result // indexes from ar1[] and ar2[] // respectively let res_l, res_r; // Start from left side of ar1[] and // right side of ar2[] let l = 0, r = n-1; while (l<m && r>=0) { // If this pair is closer to // x than the previously // found closest, then update // res_l, res_r and diff if (Math.abs(ar1[l] + ar2[r] - x) < diff) { res_l = l; res_r = r; diff = Math.abs(ar1[l] + ar2[r] - x); } // If sum of this pair is more than x, // move to smaller side if (ar1[l] + ar2[r] > x) r--; else // move to the greater side l++; } // Print the result document.write( "The closest pair is [" + ar1[res_l] + ", " + ar2[res_r] + "] </br>" ); } // driver code let ar1 = [1, 4, 5, 7]; let ar2 = [10, 20, 30, 40]; let m = ar1.length; let n = ar2.length; let x = 38; printClosest(ar1, ar2, m, n, x); </script> |
输出：
The closest pair is [7, 30]
两个未排序数组之间的最小差值对 本文由Harsh撰稿。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
