您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识
排列(排列五走势图带连线)
递归,排列,组合排列(排列五走势图带连线)
发布时间:2016-12-08加入收藏来源:互联网点击:
我们一起来看看,假设要从 n 选 m 的组合的解题思路
这里需要注意的是相对于全排列的每个元素都能参与排列不同,组合中的每个元素有两种状态,选中或未选中,所以形成递归分两种情况。
如果第一个元素选中,则要从之后的 n-1 个元素中选择 m-1 个元素
如果第一个元素未被选中,则需要从之后的 n-1 个元素选择 m 个元素
递归条件既然找到了,接下来我们就按递归四步曲来解下组合。
1、定义函数的功能定义以下函数为从数组 arr 中第 k 个位置开始取 m 个元素(如下的 COMBINATION_CNT)
public static final int COMBINATION_CNT = 5; // 组合中需要被选中的个数
public static void combination(int[] arr, int k, int[] select) {
}
这里我们额外引入了一个 select 数组,这个数组里的元素如果为1,则代表相应位置的元素被选中了,如果为 0 代表未选中
如图示,以上表示 arr 的第 2,3 元素被选中作为组合
2、寻找递推公式显然递推公式为
combination(arr, k,m) = (选中 k 位置的元素 +combination(arr, k+1) ) + (不选中 k 位置的元素 +combination(arr, k+1) )
那么终止条件呢,有两个
一个是被选中的元素已经等于我们要选择的组合个数了
一个是 k (开始选取的数组索引) 超出数组范围了。
3、将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中,补充后的函数如下
public static final int COMBINATION_CNT = 5; // 组合中需要被选中的个数public static void combination(int[] arr, int k, int[] select) {// 终止条件1:开始选取的数组索引 超出数组范围了if (k = arr.length) {return;}int selectNum = selectedNum(select);// 终止条件2:选中的元素已经等于我们要选择的数组个数了if (selectNum == COMBINATION_CNT) {for (int j = 0; j select.length; j++) {if (select[j] == 1) {System.out.print(arr[j]);}}System.out.print("\n");} else {// 第 k 位被选中select[k] = 1;combination(arr, k+1, select);// 第 k 位未被选中select[k] = 0;// 则从第 k+1 位选择 COMBINATION_CNT - selectNum 个元素combination(arr, k+1, select);}}public static void main(String[] args) {int arr = {1,2,3,4,5,6,7,8,9};int select = {0,0,0,0,0,0,0,0,0};// 一开始从 0 开始选 组合数combination(arr, 0, select);}4、求时间/空间复杂度空间复杂度:由于我们用了一个辅助数组 select, 所以空间复杂度是 O(n)时间复杂度:可以看到 f(n) = 2f(n-1),所以时间复杂度是O(2^n),显然是指数级别的
画外音:大家可以考虑一下怎么优化,提示:每种元素只有选中和被选中的状态,是不是对应了二进制的 0 和 1,可以考虑用位运算
面试中排列组合的一些变形经过以上的讲解,我相信大家对排列组合的递归解法应该是很明白了,不过面试中面试官可能还会对排列组合稍加变形,以进一步考察你的算法水平。
考虑以下情况
在全排列时参与排列的数字都是不相同的, 如果有相同的数字(比如参与排序的是 1, 1,2,3),在使用递归进行解题时,需要进行怎样的改造;
在组合中 ,我们的题目是从 n 中选出 m 个数,如果要选出所有组合呢,比如给定 1,2,3,所有的组合是1, 2, 3, 12, 13, 23, 123, 此时以上的递归解法又该怎么改造。
声明:本文为作者投稿,版权归作者个人所有。
本文到此结束,希望对大家有所帮助呢。
下一篇:返回列表
相关链接 |
||
网友回复(共有 0 条回复) |