資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式：從合併排列中查詢排列
假設我們有一個包含 2n 個元素的陣列 A。我們知道前 n 個自然數的排列是一組數字，其中儲存了 1 到 n，並且它們以任意順序排列。在陣列 A 中，合併了兩個大小為 n 的排列。當它們合併時，元素的相對順序保持不變。因此，如果排列 p 類似於 p = [3,1,2]，則一些可能的結果是：[3,1,2,3,1,2]、[3,3,1,1,2,2]、[3,1,3,1,2,2]。以下序列不是合併的可能結果：[1,3,2,1,2,3]、[3,1,2,3,2,1]、[3,3,1,2,2,1]，因為它們的相對順序不同。從 A 中，我們必須恢復排列，並且它是唯一的。
問題類別
給定的問題是分治問題的示例，我們可以使用動態規劃來解決。動態規劃是一種分治技術，其中特定問題被分解成子問題，然後解決。正常的分治技術和動態規劃之間存在差異，即後者解決了重疊的子問題並在需要時再次使用該結果。為了儲存這些重疊子問題的結果，動態規劃技術使用一個表，這個過程稱為“記憶化”。每次需要解決子問題時都會檢查表中的資料。通常，動態規劃技術用於最佳化問題，其中必須找到解決方案的最優值。這種程式設計技術的示例包括斐波那契數列問題、Bellman-Ford 單源最短路徑問題、矩陣鏈乘法問題、最長公共子序列問題等。
https://tutorialspoint.tw/data_structures_algorithms/dynamic_programming.htm
步驟
為了解決這個問題，我們將遵循以下步驟 -
n := size of A Define an array b of size: 51 fill with 0 for initialize i := 0, when i < 2 * n, update (increase i by 1), do: a := A[i] if b[a] is same as 0, then: print a b[a] := 1
示例
讓我們看看以下實現以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A){
int n = A.size() / 2;
bool b[51] = { 0 };
for (int i = 0; i < 2 * n; i++){
int a = A[i];
if (b[a] == 0)
cout << a << ", ";
b[a] = 1;
}
}
int main(){
vector<int> A = { 1, 3, 1, 4, 3, 4, 2, 2 };
solve(A);
}輸入
{ 1, 3, 1, 4, 3, 4, 2, 2 }輸出
1, 3, 4, 2,
更新於: 2022年4月8日
203 次瀏覽
廣告