数据结构
网络
关系数据库管理系统
操作系统
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.com/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 次浏览
广告