資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中從兩個陣列中最大化唯一對
問題陳述
給定兩個大小為N的陣列，使用它們的元素構成最大數量的對，每個陣列中的一個元素最多使用一次，並且用於構成對的所選元素之間的絕對差小於或等於給定元素K。
示例
如果輸入為：
arr1[] = {3, 4, 5, 2, 1}
arr2[] = {6, 5, 4, 7, 15}
並且k = 3，那麼我們可以形成以下4對，其絕對差小於或等於3：
(1, 4), (2, 5), (3, 6), (4, 7)
演算法
我們可以使用遞迴方法來解決這個問題。
- 對兩個陣列進行排序。
- 將第一個陣列的每個元素與第二個陣列的每個元素進行比較，查詢可能的對，如果可以形成對。
- 繼續檢查第一個陣列的下一個元素的下一個可能的對。
示例
讓我們來看一個例子：
#include <bits/stdc++.h>
using namespace std;
int getMaxUniquePairs(int *arr1, int *arr2, int n, int k) {
sort(arr1, arr1 + n);
sort(arr2, arr2 + n);
bool visited[n];
memset(visited, false, sizeof(visited));
int pairCnt = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (abs(arr1[i] - arr2[j]) <= k &&
visited[j] == false) {
++pairCnt;
visited[j] = true;
break;
}
}
}
return pairCnt;
}
int main() {
int arr1[] = {3, 4, 5, 2, 1};
int arr2[] = {6, 5, 4, 7, 15};
int n = sizeof(arr1) / sizeof(arr1[0]);
int k = 3;
cout << "Maximum unique pairs = " << getMaxUniquePairs(arr1, arr2, n, k) << endl;
return 0;
}輸出
Maximum unique pairs = 4
更新於：2019-12-31
瀏覽量：285
廣告