資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式列印唯一整數對
假設我們有兩個陣列a和b，每個陣列包含n個整數。我們需要從這些陣列中建立整數對，其中一個數字來自陣列a，另一個數字來自陣列b，並且它們的和始終是唯一的。我們列印所有這樣的整數對。
問題類別
上述問題可以透過應用貪心演算法解決。貪心演算法是一種選擇當前最佳解而不是遍歷所有可能解的演算法。貪心演算法也用於解決最佳化問題，類似於其更強大的兄弟動態規劃。在動態規劃中，需要遍歷所有可能的子問題以找到最優解，但它有一個缺點：它需要更多的時間和空間。因此，在各種情況下，貪心演算法被用來找到問題的最優解。雖然它並非在所有情況下都能給出最優解，但如果設計得當，它可以比動態規劃更快地產生解。貪心演算法為最佳化問題提供區域性最優解。這種技術的示例包括克魯斯卡爾和普里姆最小生成樹 (MST) 演算法、霍夫曼樹編碼、迪傑斯特拉單源最短路徑問題等。
https://tutorialspoint.tw/data_structures_algorithms/greedy_algorithms.htm
https://tutorialspoint.tw/data_structures_algorithms/dynamic_programming.htm
因此，如果我們問題的輸入是這樣的：n = 6，a = {7, 6, 5, 2, 1, 4}，b = {2, 4, 8, 9, 3, 6}，那麼輸出將是
1,2 2,3 4,4 5,6 6,8 7,9
步驟
為了解決這個問題，我們將遵循以下步驟：
sort the array a sort the array b for initialize i := 0, when i < n, update (increase i by 1), do: print(a[i], b[i])
示例
讓我們看下面的實現來更好地理解：
#include<bits/stdc++.h>
using namespace std;
void solve(int n, int a[], int b[]) {
sort(a, a + n);
sort(b, b + n);
for(int i = 0; i < n; i++)
cout<< a[i] << "," << b[i] << endl;
}
int main() {
int n = 6, a[] = {7, 6, 5, 2, 1, 4}, b[] = {2, 4, 8, 9, 3, 6};
solve(n, a, b);
return 0;
}輸入
6, {7, 6, 5, 2, 1, 4}, {2, 4, 8, 9, 3, 6}輸出
1,2 2,3 4,4 5,6 6,8 7,9
更新於：2022年4月7日
262 次瀏覽
廣告