给定一个已排序的数组和一个数字x，在数组中找到总和最接近x的偶对
原文： https://www.geeksforgeeks.org/given-sorted-array-number-x-find-pair-array-whose-sum-closest-x/
给定一个已排序的数组和一个数字x，请在数组中找到总和最接近x的一对。
例子：
Input: arr[] = {10, 22, 28, 29, 30, 40}, x = 54
Output: 22 and 30
Input: arr[] = {1, 3, 4, 7, 10}, x = 15
Output: 4 and 10
一个简单的解决方案是考虑每对，并跟踪最接近的一对（对和和x之间的绝对差最小）。 最后打印最接近的一对。 该解决方案的时间复杂度为O(n^2)。
一个有效的解决方案可以在O(n)的时间内找到该对。 这个想法类似于此帖子的方法 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: l = 0
(b) Initialize second the rightmost index: r = n-1
3) Loop while l < r.
(a) If abs(arr[l] + arr[r] - sum) < diff then
update diff and result
(b) Else if(arr[l] + arr[r] < sum ) then l++
(c) Else r--
以下是上述算法的实现。
C++
// Simple C++ program to find the pair with sum closest to a given no.
#include <bits/stdc++.h>
using namespace std;
// Prints the pair with sum closest to x
void printClosest(int arr[], int n, int x)
{
int res_l, res_r; // To store indexes of result pair
// Initialize left and right indexes and difference between
// pair sum and x
int l = 0, r = n-1, diff = INT_MAX;
// While there are elements between l and r
while (r > l)
{
// Check if this pair is closer than the closest pair so far
if (abs(arr[l] + arr[r] - x) < diff)
{
res_l = l;
res_r = r;
diff = abs(arr[l] + arr[r] - x);
}
// If this pair has more sum, move to smaller values.
if (arr[l] + arr[r] > x)
r--;
else // Move to larger values
l++;
}
cout <<" The closest pair is " << arr[res_l] << " and " << arr[res_r];
}
// Driver program to test above functions
int main()
{
int arr[] = {10, 22, 28, 29, 30, 40}, x = 54;
int n = sizeof(arr)/sizeof(arr[0]);
printClosest(arr, n, x);
return 0;
}
Java
// Java program to find pair with sum closest to x
import java.io.*;
import java.util.*;
import java.lang.Math;
class CloseSum {
// Prints the pair with sum cloest to x
static void printClosest(int arr[], int n, int x)
{
int res_l=0, res_r=0; // To store indexes of result pair
// Initialize left and right indexes and difference between
// pair sum and x
int l = 0, r = n-1, diff = Integer.MAX_VALUE;
// While there are elements between l and r
while (r > l)
{
// Check if this pair is closer than the closest pair so far
if (Math.abs(arr[l] + arr[r] - x) < diff)
{
res_l = l;
res_r = r;
diff = Math.abs(arr[l] + arr[r] - x);
}
// If this pair has more sum, move to smaller values.
if (arr[l] + arr[r] > x)
r--;
else // Move to larger values
l++;
}
System.out.println(" The closest pair is "+arr[res_l]+" and "+ arr[res_r]);
}
// Driver program to test above function
public static void main(String[] args)
{
int arr[] = {10, 22, 28, 29, 30, 40}, x = 54;
int n = arr.length;
printClosest(arr, n, x);
}
}
/*This code is contributed by Devesh Agrawal*/
Python3
# Python3 program to find the pair
# with sum
# closest to a given no.
# A sufficiently large value greater
# than any
# element in the input array
MAX_VAL = 1000000000
#Prints the pair with sum closest to x
def printClosest(arr, n, x):
# To store indexes of result pair
res_l, res_r = 0, 0
#Initialize left and right indexes
# and difference between
# pair sum and x
l, r, diff = 0, n-1, MAX_VAL
# While there are elements between l and r
while r > l:
# Check if this pair is closer than the
# closest pair so far
if abs(arr[l] + arr[r] - x) < diff:
res_l = l
res_r = r
diff = abs(arr[l] + arr[r] - x)
if arr[l] + arr[r] > x:
# If this pair has more sum, move to
# smaller values.
r -= 1
else:
# Move to larger values
l += 1
print('The closest pair is {} and {}'
.format(arr[res_l], arr[res_r]))
# Driver code to test above
if __name__ == "__main__":
arr = [10, 22, 28, 29, 30, 40]
n = len(arr)
x=54
printClosest(arr, n, x)
# This code is contributed by Tuhin Patra
C#
// C# program to find pair with sum closest to x
using System;
class GFG {
// Prints the pair with sum cloest to x
static void printClosest(int []arr, int n, int x)
{
// To store indexes of result pair
int res_l = 0, res_r = 0;
// Initialize left and right indexes and
// difference between pair sum and x
int l = 0, r = n-1, diff = int.MaxValue;
// While there are elements between l and r
while (r > l)
{
// Check if this pair is closer than the
// closest pair so far
if (Math.Abs(arr[l] + arr[r] - x) < diff)
{
res_l = l;
res_r = r;
diff = Math.Abs(arr[l] + arr[r] - x);
}
// If this pair has more sum, move to
// smaller values.
if (arr[l] + arr[r] > x)
r--;
else // Move to larger values
l++;
}
Console.Write(" The closest pair is " +
arr[res_l] + " and " + arr[res_r]);
}
// Driver program to test above function
public static void Main()
{
int []arr = {10, 22, 28, 29, 30, 40};
int x = 54;
int n = arr.Length;
printClosest(arr, n, x);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// Simple PHP program to find the
// pair with sum closest to a
// given no.
// Prints the pair with
// sum closest to x
function printClosest($arr, $n, $x)
{
// To store indexes
// of result pair
$res_l;
$res_r;
// Initialize left and right
// indexes and difference between
// pair sum and x
$l = 0;
$r = $n - 1;
$diff = PHP_INT_MAX;
// While there are elements
// between l and r
while ($r > $l)
{
// Check if this pair is closer
// than the closest pair so far
if (abs($arr[$l] + $arr[$r] - $x) <
$diff)
{
$res_l = $l;
$res_r = $r;
$diff = abs($arr[$l] + $arr[$r] - $x);
}
// If this pair has more sum,
// move to smaller values.
if ($arr[$l] + $arr[$r] > $x)
$r--;
// Move to larger values
else
$l++;
}
echo " The closest pair is "
, $arr[$res_l] ," and "
, $arr[$res_r];
}
// Driver Code
$arr = array(10, 22, 28, 29, 30, 40);
$x = 54;
$n = count($arr);
printClosest($arr, $n, $x);
// This code is contributed by anuj_67\.
?>
输出：
The closest pair is 22 and 30
版权属于：月萌API www.moonapi.com，转载请注明出处
