下你所需,载你所想!
汇集开发技术源码资料

互换法解决m选n组合问题

:2.213KB :1 :2021-08-31 14:29:10

部分简介

使用0或1表示集合中的元素是否出现在选出的集合中,因此一个0/1列表即可表示选出哪些元素。
例如:[1 2 3 4 5],选出的元素是[1 2 3]那么列表就是[1 1 1 0 0]。
使用01交换法的思路是,首先用一个数组用于记录集合中某元素是否被选中。
因为需要在m个元素中选择n个,所以这个数组中总共有n个为1的元素,其他均为0。
因此在初始化过程中,将该数组前n个元素赋值为1,其余m-n个元素赋值为0。
然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为“01”组合,同时将其左边的所有“1”全部移动到数组的最左端。
当第一个“1”移动到数组的m-n+1的位置,即n个“1”全部移动到最右端时,就得到了最后一个组合。
这个算法相比递归算法的最大好处是,对大数据的运算能力比较强。用递归算法,当数据量很大,递归层数太多时,就容易出现堆栈溢出的情况,而这个算法面对大量数据,虽然可能会慢,但稳定性好,只要等,就会一直算。

互换法解决m选n组合问题

热门推荐

相关文章