資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中從兩個陣列中計數和等於K的數對
給定兩個陣列Arr1[]和Arr2[]以及一個數字K。目標是找到兩個陣列元素的唯一數對，使得它們的和為K。數對的形式為(Arr1[i], Arr2[j])，其中Arr1[i]+Arr2[j]==K。
我們將使用兩個迴圈遍歷i和j。如果和(Arr1[i]+Arr2[j])==K，並且該數對不存在於unordered_map<int,int>中。將其新增到map中並遞增計數。
讓我們透過例子來理解。
輸入
Arr1[]={ 1,3,2,4,3,2 }; Arr2[]={ 0,2,1,2,3 }; K=4輸出
Number of pairs with sum K : 4
說明
Pairs will be ( Arr1[0], Arr2[4] ) → (1,3) ( Arr1[1], Arr2[2] ) → (3,1) ( Arr1[2], Arr2[1] ) → (2,2) ( Arr1[3], Arr2[2] ) → (3,1) All other pairs already exist.Total unique pairs 4.
輸入
Arr1[]={ 0,2,1,2,3}; Arr2[]={ 1,1,1,1,1 }; K=3輸出
Number of pairs with sum K : 1
說明
Pairs will be ( Arr1[1], Arr2[0] ) → (2,1) All other pairs already exist.Total unique pairs 1.
下面程式中使用的演算法如下
我們取兩個陣列Arr1[]和Arr2[]以及一個用於求和的變數K。
Len1和Len2用於表示兩個陣列的長度。
函式pairsumisK(int arr1[],int arr2[],int k,int l1,int l2)獲取所有變數並返回兩個陣列中和為k的唯一元素對的計數。
將初始變數count設定為0，表示數對的數量。
使用unordered_map umap儲存唯一數對。
使用兩個for迴圈遍歷兩個陣列。
對於arr1[]中的元素，從i=0到i<len1。對於arr2[]中的元素，從j=0到j<len2。
檢查arr1[i]+arr2[j]=k是否成立。如果成立，則檢查該數對是否透過umap.find(....)==umap.end()存在。
如果不存在，則將該數對新增到umap中並遞增計數。
在所有迴圈結束後，count將包含此類數對的總數。
返回計數作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
int pairsumisK(int arr1[],int arr2[],int k,int l1,int l2){
int count = 0;
unordered_map<int, int> umap;
for (int i = 0; i < l1; i++){
for (int j = 0; j < l2; j++){
int sum=arr1[i]+arr2[j];
if(sum==k) //pairs with sum=k only{
if(umap.find(arr1[i]) == umap.end()) //unique pairs only{
umap.insert(make_pair(arr1[i],arr2[j]));
}
}
}
}
return count;
}
int main(){
int Arr1[]={ 1,2,3,0,2,4 };
int Arr2[]={ 3,2,5,2 };
int len1=sizeof(Arr1)/sizeof(Arr1[0]);
int len2=sizeof(Arr2)/sizeof(Arr2[0]);
int K=5; //length of array
cout <<endl<< "Number of pairs with sum K : "<<pairsumisK(Arr1,Arr2,K,len1,len2);
return 0;
}輸出
如果我們執行上述程式碼，它將生成以下輸出：
Number of pairs with sum K : 0
更新於：2020年10月31日
242 次瀏覽
廣告