给定一个由N个数字和一个整数K组成的数组。任务是打印长度为K的唯一子序列的数量。
null
例如：
Input : a[] = {1, 2, 3, 4}, k = 3 Output : 4. Unique Subsequences are: {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}Input: a[] = {1, 1, 1, 2, 2, 2 }, k = 3Output : 4 Unique Subsequences are {1, 1, 1}, {1, 1, 2}, {1, 2, 2}, {2, 2, 2}
方法： 有一个众所周知的公式，可以从N个唯一的对象中选择多少个固定长度K的子序列。但这里的问题有几个不同之处。其中之一是子序列中的顺序很重要，必须像原始序列一样保留。对于这样的问题，不可能有现成的组合公式，因为结果取决于原始数组的顺序。
其主要思想是根据子序列的长度进行反复处理。在每一个重复步骤中，从末尾移动到开头，并使用上一步中较短的唯一组合计数来计算唯一组合。更严格地说，在每一步j上，我们保持一个长度为N的数组，p处的每一个元素意味着我们在i处元素的右边发现了多少长度为j的唯一子序列，包括i本身。
以下是上述方法的实施情况。
C++
#include <bits/stdc++.h> using namespace std; // Function which returns the numbe of // unique subsequences of length K int solution(vector< int >& A, int k) { // seiz of the vector // which does is constant const int N = A.size(); // bases cases if (N < k || N < 1 || k < 1) return 0; if (N == k) return 1; // Prepare arrays for recursion vector< int > v1(N, 0); vector< int > v2(N, 0); vector< int > v3(N, 0); // initiate separately for k = 1 // initiate the last element v2[N - 1] = 1; v3[A[N - 1] - 1] = 1; // initiate all other elements of k = 1 for ( int i = N - 2; i >= 0; i--) { // initialize the front element // to vector v2 v2[i] = v2[i + 1]; // if element v[a[i]-1] is 0 // then increment it in vector v2 if (v3[A[i] - 1] == 0) { v2[i]++; v3[A[i] - 1] = 1; } } // iterate for all possible values of K for ( int j = 1; j < k; j++) { // fill the vectors with 0 fill(v3.begin(), v3.end(), 0); // fill(v1.begin(), v1.end(), 0) // the last must be 0 as from last no unique // subarray can be formed v1[N - 1] = 0; // Iterate for all index from which unique // subsequences can be formed for ( int i = N - 2; i >= 0; i--) { // add the number of subsequence formed // from the next index v1[i] = v1[i + 1]; // start with combinations on the // next index v1[i] = v1[i] + v2[i + 1]; // Remove the elements which have // already been counted v1[i] = v1[i] - v3[A[i] - 1]; // Update the number used v3[A[i] - 1] = v2[i + 1]; } // prepare the next iteration // by filling v2 in v1 v2 = v1; } // last answer is stored in v2 return v2[0]; } // Function to push the vector into an array // and print all the unique subarrays void solve( int a[], int n, int k) { vector< int > v; // fill the vector with a[] v.assign(a, a + n); // Function call to print the count // of unique subsequences of size K cout << solution(v, k); } // Driver Code int main() { int a[] = { 1, 2, 3, 4 }; int n = sizeof (a) / sizeof (a[0]); int k = 3; solve(a, n, k); return 0; } |
JAVA
import java.util.*; class GFG{ // Function which returns the numbe of // unique subsequences of length K static int solution( int [] A, int N, int k) { // Bases cases if (N < k || N < 1 || k < 1 ) return 0 ; if (N == k) return 1 ; // Prepare arrays for recursion int [] v1 = new int [N]; int [] v2 = new int [N]; int [] v3 = new int [N]; // Initiate separately for k = 1 // initiate the last element v2[N - 1 ] = 1 ; v3[A[N - 1 ] - 1 ] = 1 ; // Initiate all other elements of k = 1 for ( int i = N - 2 ; i >= 0 ; i--) { // Initialize the front element // to vector v2 v2[i] = v2[i + 1 ]; // If element v[a[i]-1] is 0 // then increment it in vector v2 if (v3[A[i] - 1 ] == 0 ) { v2[i]++; v3[A[i] - 1 ] = 1 ; } } // Iterate for all possible values of K for ( int j = 1 ; j < k; j++) { // Fill the vectors with 0 Arrays.fill(v3, 0 ); // Fill(v1.begin(), v1.end(), 0) // the last must be 0 as from last // no unique subarray can be formed v1[N - 1 ] = 0 ; // Iterate for all index from which // unique subsequences can be formed for ( int i = N - 2 ; i >= 0 ; i--) { // Add the number of subsequence // formed from the next index v1[i] = v1[i + 1 ]; // Start with combinations on the // next index v1[i] = v1[i] + v2[i + 1 ]; // Remove the elements which have // already been counted v1[i] = v1[i] - v3[A[i] - 1 ]; // Update the number used v3[A[i] - 1 ] = v2[i + 1 ]; } } // Last answer is stored in v2 return v2[ 0 ]; } // Driver Code public static void main(String[] args) { int a[] = { 1 , 2 , 3 , 4 }; int n = a.length; int k = 3 ; System.out.print(solution(a, n, k)); } } // This code is contributed by amal kumar choubey |
Python3
# Function which returns the numbe of # unique subsequences of length K def solution( A, k): # seiz of the vector # which does is constant N = len (A) # bases cases if (N < k or N < 1 or k < 1 ): return 0 if (N = = k): return 1 # Prepare arrays for recursion v1 = [ 0 ] * (N) v2 = [ 0 ] * N v3 = [ 0 ] * N # initiate separately for k = 1 # initiate the last element v2[N - 1 ] = 1 v3[A[N - 1 ] - 1 ] = 1 # initiate all other elements of k = 1 for i in range (N - 2 , - 1 , - 1 ): # initialize the front element # to vector v2 v2[i] = v2[i + 1 ] # if element v[a[i]-1] is 0 # then increment it in vector v2 if (v3[A[i] - 1 ] = = 0 ): v2[i] + = 1 v3[A[i] - 1 ] = 1 # iterate for all possible values of K for j in range ( 1 , k) : # fill the vectors with 0 v3 = [ 0 ] * N # fill(v1.begin(), v1.end(), 0) # the last must be 0 as from last no unique # subarray can be formed v1[N - 1 ] = 0 # Iterate for all index from which unique # subsequences can be formed for i in range ( N - 2 , - 1 , - 1 ) : # add the number of subsequence formed # from the next index v1[i] = v1[i + 1 ] # start with combinations on the # next index v1[i] = v1[i] + v2[i + 1 ] # Remove the elements which have # already been counted v1[i] = v1[i] - v3[A[i] - 1 ] # Update the number used v3[A[i] - 1 ] = v2[i + 1 ] # prepare the next iteration # by filling v2 in v1 for i in range ( len (v1)): v2[i] = v1[i] # last answer is stored in v2 return v2[ 0 ] # Function to push the vector into an array # and print all the unique subarrays def solve(a, n, k): # fill the vector with a[] v = a # Function call to print the count # of unique subsequences of size K print ( solution(v, k)) # Driver Code if __name__ = = "__main__" : a = [ 1 , 2 , 3 , 4 ] n = len (a) k = 3 solve(a, n, k) # This code is contributed by chitranayal |
C#
using System; class GFG{ // Function which returns the numbe of // unique subsequences of length K static int solution( int [] A, int N, int k) { // Bases cases if (N < k || N < 1 || k < 1) return 0; if (N == k) return 1; // Prepare arrays for recursion int [] v1 = new int [N]; int [] v2 = new int [N]; int [] v3 = new int [N]; // Initiate separately for k = 1 // initiate the last element v2[N - 1] = 1; v3[A[N - 1] - 1] = 1; // Initiate all other elements of k = 1 for ( int i = N - 2; i >= 0; i--) { // Initialize the front element // to vector v2 v2[i] = v2[i + 1]; // If element v[a[i]-1] is 0 // then increment it in vector v2 if (v3[A[i] - 1] == 0) { v2[i]++; v3[A[i] - 1] = 1; } } // Iterate for all possible values of K for ( int j = 1; j < k; j++) { // Fill the vectors with 0 for ( int i = 0; i < v3.GetLength(0); i++) v3[i] = 0; // Fill(v1.begin(), v1.end(), 0) // the last must be 0 as from last // no unique subarray can be formed v1[N - 1] = 0; // Iterate for all index from which // unique subsequences can be formed for ( int i = N - 2; i >= 0; i--) { // Add the number of subsequence // formed from the next index v1[i] = v1[i + 1]; // Start with combinations on the // next index v1[i] = v1[i] + v2[i + 1]; // Remove the elements which have // already been counted v1[i] = v1[i] - v3[A[i] - 1]; // Update the number used v3[A[i] - 1] = v2[i + 1]; } } // Last answer is stored in v2 return v2[0]; } // Driver Code public static void Main(String[] args) { int []a = { 1, 2, 3, 4 }; int n = a.Length; int k = 3; Console.Write(solution(a, n, k)); } } // This code is contributed by Rohit_ranjan |
Javascript
<script> // Function which returns the numbe of // unique subsequences of length K function solution(A, N, K) { // Bases cases if (N < k || N < 1 || k < 1) return 0; if (N == k) return 1; // Prepare arrays for recursion let v1 = new Array(N); let v2 = new Array(N); let v3 = new Array(N); for (let i = 0; i < N; i++) { v1[i] = 0; v2[i] = 0; v3[i] = 0; } // Initiate separately for k = 1 // initiate the last element v2[N - 1] = 1; v3[A[N - 1] - 1] = 1; // Initiate all other elements of k = 1 for (let i = N - 2; i >= 0; i--) { // Initialize the front element // to vector v2 v2[i] = v2[i + 1]; // If element v[a[i]-1] is 0 // then increment it in vector v2 if (v3[A[i] - 1] == 0) { v2[i]++; v3[A[i] - 1] = 1; } } // Iterate for all possible values of K for (let j = 1; j < k; j++) { // Fill the vectors with 0 for (let i = 0; i < v3.length; i++) { v3[i] = 0; } // Fill(v1.begin(), v1.end(), 0) // the last must be 0 as from last // no unique subarray can be formed v1[N - 1] = 0; // Iterate for all index from which // unique subsequences can be formed for (let i = N - 2; i >= 0; i--) { // Add the number of subsequence // formed from the next index v1[i] = v1[i + 1]; // Start with combinations on the // next index v1[i] = v1[i] + v2[i + 1]; // Remove the elements which have // already been counted v1[i] = v1[i] - v3[A[i] - 1]; // Update the number used v3[A[i] - 1] = v2[i + 1]; } } // Last answer is stored in v2 return v2[0]; } // Driver Code let a = [ 1, 2, 3, 4 ]; let n = a.length; let k = 3; document.write(solution(a, n, k)); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
4
时间复杂性： O（N*K） 辅助空间： O（N）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
