資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中最大和的配對數量
我們需要找到在給定整數陣列中所有具有最大和的配對的數量。一個配對由兩個數字組成，而和則僅僅是將它們相加的結果。
我們將看到解決此問題的多種方案，從樸素（暴力）方法開始，然後轉向更最佳化的方案。以下是我們將在本文中介紹的方法列表：
示例
輸入
arr = [3, 6, 5, 2, 1, 2, 3, 4, 1, 5]
輸出
2
任何配對的最大和為 10。兩個配對給出此和：(5, 5) 和 (6, 4)。因此，答案為 2。
使用兩個迴圈的暴力方法
暴力解法是最容易理解的一種。在這裡，我們嘗試陣列中的每個可能的配對並計算它們的和。我們跟蹤遇到的最高和。一旦我們知道最大和是多少，我們再次遍歷陣列並檢查每個配對的和是否與最大值匹配，如果匹配，我們增加配對的數量。
讓我們看看在 C++ 中計算最大和配對的過程
- 初始化最大和： 我們首先將最大和設定為一個非常小的數字，例如
INT_MIN（最小的可能整數值）。這確保我們遇到的第一個配對將始終更新最大和。 - 查詢最大和： 我們使用兩個迴圈。第一個迴圈選擇一個數字，第二個迴圈選擇另一個數字（在第一個數字之後）。對於每個配對，我們計算和並將其與當前最大和進行比較。如果它更大，我們更新最大和。
- 計算具有最大和的配對數量： 找到最大和後，我們重置迴圈並再次檢查每個配對的和。這次，我們計算有多少個配對給我們最大和。
程式碼實現
#include<bits/stdc++.h>
using namespace std;
int maxSumPairsCnt(int a[], int n) {
int maxSum = INT_MIN;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
maxSum = max(maxSum, a[i] + a[j]);
}
}
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] + a[j] == maxSum) {
cnt++;
}
}
}
return cnt;
}
int main() {
int arr[] = {3, 4, 5, 2, 1, 2, 3, 4, 1, 5};
int n = 10;
cout << maxSumPairsCnt(arr, n) << endl;
return 0;
}
時間複雜度
此方法的時間複雜度為 O(n²)，其中 n 是陣列的大小。這是因為我們使用了兩個巢狀迴圈來檢查每個可能的數字配對。雖然此解決方案很簡單，但隨著陣列大小的增加，它會變得緩慢。
說明
我們使用了一種暴力方法，其中檢查、計算並比較了陣列中的每個配對以查詢最大和。一旦我們得到最大和，我們再次迴圈遍歷陣列以計算有多少個配對具有此和。雖然這很簡單且友好，但由於檢查所有可能的配對的雙重迴圈，其時間複雜度為 O(n²) 。此方法適用於小型陣列，但隨著大小的增加會變得效率低下。
使用排序的最大和配對
我們可以透過首先對陣列進行排序來改進我們的解決方案。一旦陣列排序，兩個最大的元素將是陣列中的最後兩個元素。它們的和將是最大配對和。
排序還使計算有多少個配對具有此和變得更容易，因為類似的數字將被分組在一起。
- 對陣列進行排序： 排序後，陣列的最後兩個元素將給出最大和。
- 計算配對： 我們現在使用兩個迴圈遍歷陣列來計算有多少個數字配對的和等於此值。
現在，我們瞭解了我們必須做什麼，所以讓我們透過程式碼來理解 -
#include<bits/stdc++.h>
using namespace std;
int maxSumPairsCnt(int a[], int n) {
sort(a, a + n); // Sort the array
int maxSum = a[n - 1] + a[n - 2]; // Sum of two largest elements
int cnt = 0;
// Count pairs with the max sum
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] + a[j] == maxSum) {
cnt++;
}
}
}
return cnt;
}
int main() {
int arr[] = {3, 4, 5, 2, 1, 2, 3, 4, 1, 5};
int n = 10;
cout << maxSumPairsCnt(arr, n) << endl;
return 0;
}
時間複雜度
對陣列進行排序的時間複雜度為 O(n log n)，而由於巢狀迴圈，計算配對仍然需要 O(n²)。排序加快了查詢最大和的速度，但我們仍然需要兩個迴圈來計算配對。
說明
透過對陣列進行排序，我們可以使用排序列表末尾的兩個最大元素快速識別最大和。但是，我們仍然需要迴圈遍歷所有配對以計算有多少個配對的和等於此最大值。排序提高了查詢最大和的速度，但並沒有完全最佳化計數過程，導致排序的時間複雜度為 O(n log n)，計數的時間複雜度為 O(n²) 。
使用雜湊對映的最大和配對
此方法使用雜湊對映來計算陣列中每個元素的頻率。透過儲存每個數字出現的次數，我們可以有效地找到具有最大和的配對，而無需使用兩個迴圈。
- 計算每個元素的頻率： 使用雜湊對映跟蹤每個數字出現的次數。
- 查詢最大元素： 陣列中的兩個最大元素將給出最大和。我們在雜湊對映中查詢它們。
- 計算配對： 基於兩個最大數字的頻率，我們計算可以形成多少個配對。如果這兩個數字相同，我們使用組合公式
nC2（兩個的組合）。如果它們不同，我們只需將它們的頻率相乘。
以下是使用雜湊對映查詢最大和配對數量的程式碼。
#include <bits/stdc++.h>
using namespace std;
int maxSumPairsCnt(int a[], int n) {
unordered_map freq;
// Count the frequency of each element
for (int i = 0; i < n; i++) {
freq[a[i]]++;
}
// Find the two largest elements
int max1 = INT_MIN, max2 = INT_MIN;
for (auto it : freq) {
if (it.first > max1) {
max2 = max1;
max1 = it.first;
} else if (it.first > max2) {
max2 = it.first;
}
}
// Calculate the maximum sum
int maxSum = max1 + max2;
int cnt = 0;
// Count pairs
if (max1 == max2) {
cnt = (freq[max1] * (freq[max1] - 1)) / 2; // nC2 combinations
} else {
cnt = freq[max1] * freq[max2];
}
return cnt;
}
int main() {
int arr[] = {3, 4, 5, 2, 1, 2, 3, 4, 1, 5};
int n = 10;
cout << maxSumPairsCnt(arr, n) << endl;
return 0;
}
時間複雜度
時間複雜度為 O(n)
這是因為我們只需要遍歷陣列一次來計算每個元素的頻率，然後我們進行恆定次數的操作（查詢兩個最大元素並計算配對的數量）。因此，此方法比以前的方法快得多。
說明
此方法使用雜湊對映來計算陣列中每個元素的頻率。然後，我們透過掃描頻率對映一次來找到兩個最大元素。最後，我們使用這兩個元素（如果它們相同則使用相同的元素）計算可以形成多少個配對。此方法避免了雙重迴圈並實現了 O(n) 的時間複雜度，使其成為大型資料集最快、最有效的方法。
352 次檢視
