如何求数列的子数列个数
本帖最后由 RIXO 于 2019-4-16 10:44 编辑数列就是一串数字的集合，子数列就是他不改变相对顺序下的子集
例如 （1，2，1）
子数列为 （1）（2）（1，2）（2，1）（1，1）（1，2，1）
个数为6
我的数列是无序数列，且里面的每个值都小于等于5，即可能值为 0，1，2，3，4，5
想求一个效率高一点的算法。
如果可以尽量用C和C++，java我还没学。{:9_222:} 本帖最后由 Croper 于 2019-4-16 18:01 编辑
使用动态规划解决，效率要高得多
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;
//动态规划
//从size为1的子集开始，now记录以当前节点结束的新增子集的数目
//当size增加时，now变为pre，并通过pre推出新的now
int GetSubArrCount(vector<int> v) {
vector<int> pre(v.size()+1, 0);
pre = 1; //当子集的size为0时，只有1个子集，空集
int sum = 0;
for (int i = 0; i <= v.size(); ++i) {
vector<int> now(v.size() - i, 0);
for (int j = 0; j < pre.size()-1; ++j) {//遍历pre的元素，当元素不为0时，考虑此元素与之后的每一个不重复的元素都能构成新的不重复子集
if (pre == 0) continue;
unordered_map<int, bool> map;
for (int k = 0; k < pre.size()-1 - j; ++k) {
int a = v;
if (map == false) {
map = true;
now += pre;
sum += pre;
}
}
}
pre = move(now);
}
return sum;
}
int main() {
vector<int> v = { 1,3,2,5,3,1,4,2,5};
int i = GetSubArrCount(v);
cout << i;
system("pause");
} 本帖最后由 Croper 于 2019-4-16 13:34 编辑
如果没有不重复的要求德话直接套公式n*(n+1)/2就好了啊
//====================================分割线================================
上电脑端，看了一下，你的要求好像是要求子序列不重复且子序列是非连续子序列
首先提供一个使用stl的办法
#include <vector>
#include <set>
#include <iostream>
using namespace std;
//这种方法的思路相当直接：求出所有子序列，加入set，set的大小就是不重复子序列的数量
//但是效率可能稍低
int GetSubArrCount(vector<int> v) {
set<vector<int>> SubArrSet;
int N = 1 << v.size();
for (int i = 1; i < N; ++i) {
int a = i;
vector<int> SubArr;
for (int j = 0; a != 0; j++, a >>= 1) {
if ((a & 1) == 1) {
SubArr.push_back(v);
}
}
SubArrSet.insert(SubArr);
}
return SubArrSet.size();
}
int main() {
vector<int> v = { 1,2,1};
int i = GetSubArrCount(v);
cout << i;
system("pause");
} 如果下午六点前没人给你更好的代码 我就给出我的思路 挺好的 差实现了 micolar 发表于 2019-4-16 13:42
如果下午六点前没人给你更好的代码 我就给出我的思路 挺好的 差实现了
呃，你还回复不，不回复我明天可就设他为最佳答案了
页:
[1]