C ++中最大的可分割子集
假设我们有一组不同的正整数,我们必须找到最大子集,以使该子集中的每对像(Si,Sj)的元素都满足:SimodSj=0或SjmodSi=0。
因此,如果输入像[1,2,3],则可能的结果可能像[1,2]或[1,3]
为了解决这个问题,我们将遵循以下步骤-
创建一个数组ret,设置端点:=0,retLen:=1,n:=nums的大小
如果n为0,则返回空集
排序nums数组
创建大小为n的两个数组len和par,用1初始化len,用0初始化par
当我在1到n–1的范围内时
如果nums[i]modnums[j]=0且len[j]+1>len[i],则
len[i]:=len[j]+1
par[i]:=j
par[i]:=i
对于0到i–1范围内的j
如果len[j]>retLen,则retLen:=len[i]和端点:=i
将nums[endPoint]插入ret
而端点与par[endPoint]不同
端点:=par[endPoint]
将nums[endPoint]插入ret
反转列表ret并返回ret
例子(C++)
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: vector<int> largestDivisibleSubset(vector<int>& nums) { vector <int> ret; int endPoint = 0; int retLen = 1; int n = nums.size(); if(!n) return {}; sort(nums.begin(), nums.end()); vector <int> len(n, 1); vector <int> par(n, 0); for(int i = 1; i < n; i++){ par[i] = i; for(int j = 0; j < i; j++){ if(nums[i] % nums[j] == 0 && len[j] + 1 > len[i]){ len[i] = len[j] + 1; par[i] = j; } } if(len[i] > retLen){ retLen = len[i]; endPoint = i; } } ret.push_back(nums[endPoint]); while(endPoint != par[endPoint]){ endPoint = par[endPoint]; ret.push_back(nums[endPoint]); } reverse(ret.begin(), ret.end()); return ret; } }; main(){ Solution ob; vector<int> v = {1,2,3}; print_vector(ob.largestDivisibleSubset(v)); }
输入值
[1,2,3]
输出结果
[1, 2, ]