给定两个数组的大小 N 任务是找到将给定数组合并成一个数组的方法，这样每个数组的元素顺序就不会改变。 例如：
null
Input : n = 2, m = 2Output : 6Let first array of size n = 2 be [1, 2] and second array of size m = 2 be [3, 4].So, possible merged array of n + m elements can be:[1, 2, 3, 4][1, 3, 2, 4][3, 4, 1, 2][3, 1, 4, 2][1, 3, 4, 2][3, 1, 2, 4] Input : n = 4, m = 6Output : 210
这个想法是使用组合数学的概念。假设我们有两个数组A{a1，a2，…，am}和B{b1，b2，…，bn}，分别有m和n个元素，现在我们必须合并它们而不失去它们的顺序。 合并后我们知道合并后的元素总数将是（m+n）个元素。所以，现在我们只需要从（m+n）中选择m个位置，你将按照数组A的实际顺序放置元素，也就是 m+n C N . 在放置数组A的m元素后，将剩下n个空间，B数组的n个元素可以按其实际顺序填充这些空间。 所以，合并两个数组以使它们在合并数组中的顺序相同的方法的总数是 m+n C N 以下是该方法的实施情况：
C++
// CPP Program to find number of ways // to merge two array such that their // order in merged array is same #include <bits/stdc++.h> using namespace std; // function to find the binomial coefficient int binomialCoeff( int n, int k) { int C[k + 1]; memset (C, 0, sizeof (C)); C[0] = 1; // nC0 is 1 for ( int i = 1; i <= n; i++) { // Compute next row of pascal triangle // using the previous row for ( int j = min(i, k); j > 0; j--) C[j] = C[j] + C[j - 1]; } return C[k]; } // function to find number of ways // to merge two array such that their // order in merged array is same int numOfWays( int n, int m) { return binomialCoeff(m + n, m); } // Driven Program int main() { int n = 2, m = 2; cout << numOfWays(n, m) << endl; return 0; } |
JAVA
// Java Program to find number of ways // to merge two array such that their // order in merged array is same import java.io.*; class GFG { // function to find the binomial // coefficient static int binomialCoeff( int n, int k) { int C[] = new int [k + 1 ]; // memset(C, 0, sizeof(C)); C[ 0 ] = 1 ; // nC0 is 1 for ( int i = 1 ; i <= n; i++) { // Compute next row of pascal // triangle using the previous // row for ( int j = Math.min(i, k); j > 0 ; j--) C[j] = C[j] + C[j - 1 ]; } return C[k]; } // function to find number of ways // to merge two array such that their // order in merged array is same static int numOfWays( int n, int m) { return binomialCoeff(m + n, m); } // Driven Program public static void main (String[] args) { int n = 2 , m = 2 ; System.out.println(numOfWays(n, m)); } } // This code is contributed by anuj_67. |
Python3
# Python 3 Program to find number of ways # to merge two array such that their # order in merged array is same # function to find the binomial coefficient def binomialCoeff(n, k): C = [ 0 for i in range (k + 1 )] C[ 0 ] = 1 for i in range ( 1 , n + 1 , 1 ): # Compute next row of pascal # triangle using the previous row j = min (i, k) while (j > 0 ): C[j] = C[j] + C[j - 1 ] j - = 1 return C[k] # function to find number of ways # to merge two array such that their # order in merged array is same def numOfWays(n, m): return binomialCoeff(m + n, m) # Driver Code if __name__ = = '__main__' : n = 2 m = 2 print (numOfWays(n, m)) # This code is contributed by # Sahil_shelangia |
C#
// C# Program to find number of ways // to merge two array such that their // order in merged array is same using System; class GFG { // function to find the binomial // coefficient static int binomialCoeff( int n, int k) { int []C = new int [k + 1]; // memset(C, 0, sizeof(C)); C[0] = 1; // nC0 is 1 for ( int i = 1; i <= n; i++) { // Compute next row of pascal // triangle using the previous // row for ( int j = Math.Min(i, k); j > 0; j--) C[j] = C[j] + C[j - 1]; } return C[k]; } // function to find number of ways // to merge two array such that their // order in merged array is same static int numOfWays( int n, int m) { return binomialCoeff(m + n, m); } // Driven Program public static void Main () { int n = 2, m = 2; Console.WriteLine(numOfWays(n, m)); } } // This code is contributed by anuj_67. |
PHP
<?php // PHP Program to find number of ways // to merge two array such that their // order in merged array is same // function to find the binomial coefficient function binomialCoeff( $n , $k ) { $C = array ( $k + 1); for ( $i =0; $i < count ( $C ); $i ++) $C [ $i ] = 0; $C [0] = 1; // nC0 is 1 for ( $i = 1; $i <= $n ; $i ++) { // Compute next row of pascal triangle // using the previous row for ( $j = min( $i , $k ); $j > 0; $j --) $C [ $j ] = $C [ $j ] + $C [ $j - 1 ]; } return $C [ $k ]; } // function to find number of ways // to merge two array such that their // order in merged array is same function numOfWays( $n , $m ) { return binomialCoeff( $m + $n , $m ); } $n = 2; $m = 2; echo numOfWays( $n , $m ); //This code is contributed by Rajput-Ji. ?> |
Javascript
<script> // Javascript Program to find number of ways // to merge two array such that their // order in merged array is same // function to find the binomial // coefficient function binomialCoeff(n, k) { let C = new Array(k + 1); C.fill(0); // memset(C, 0, sizeof(C)); C[0] = 1; // nC0 is 1 for (let i = 1; i <= n; i++) { // Compute next row of pascal // triangle using the previous // row for (let j = Math.min(i, k); j > 0; j--) C[j] = C[j] + C[j - 1]; } return C[k]; } // function to find number of ways // to merge two array such that their // order in merged array is same function numOfWays(n, m) { return binomialCoeff(m + n, m); } let n = 2, m = 2; document.write(numOfWays(n, m)); // This code is contributed by divyeshrabadiya07. </script> |
输出：
6
我们可以在线性时间内使用 二项式系数的线性时间实现 .
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
