資料結構
網路
關係型資料庫
作業系統
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 次瀏覽
廣告