数据结构
网络
关系型数据库
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会科学
时尚研究
法律研究在 c++ 中查找两个已排序数组中最接近的一对
假设我们有两个已排序的数组和一个数字 x，我们必须找出和最接近 x 的一对。并且该对来自各个数组中。我们有两个数组 A1 [0..m-1] 和 A2 [0..n-1]，以及另一个值 x。我们必须找出成对的 A1[i] + A2[j] 其中（A1[i] + A2[j] – x）的绝对值最小。因此，如果 A1 = [1, 4, 5, 7]，和 A2 = [10, 20, 30, 40]，和 x = 32，则输出为 1 和 30。
我们将从 A1 的左边开始，从 A2 的右边开始，然后遵循以下步骤查找这样的成对
- 初始化 diff，这将保存成对和 x 之间的差异
- 初始化两个指针 left := 0 并且 right := n – 1
- while left <= m 并且 right >= 0，执行
- if |A1[left] + A2[right] – sum| < diff，则
- 更新 diff 和结果
- if (A1[left] + A2[right]) < sum，则
- left 加 1
- 否则
- right 减 1
- if |A1[left] + A2[right] – sum| < diff，则
- 显示结果
案例
#include<iostream>
#include<cmath>
using namespace std;
void findClosestPair(int A1[], int A2[], int m, int n, int x) {
int diff = INT_MAX;
int left_res, right_res;
int left = 0, right = n-1;
while (left<m && right>=0) {
if (abs(A1[left] + A2[right] - x) < diff) {
left_res = left;
right_res = right;
diff = abs(A1[left] + A2[right] - x);
}
if (A1[left] + A2[right] > x)
right--;
else
left++;
}
cout << "The closest pair is [" << A1[left_res] << ", "<< A2[right_res] << "]";
}
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 = 32;
findClosestPair(ar1, ar2, m, n, x);
}输出
The closest pair is [1, 30]
更新日期：2019 年 12 月 30 日
414 次浏览
广告