改进,从一个数组中找出 N 个数,其和为 M 的所有可能
栏目: JavaScript · 发布时间: 5年前
内容简介:从一个数组中找出 N 个数,其和为 M 的所有可能。举个例子,从数组 [1, 2, 3, 4] 中选取 2 个元素,求和为 5 的所有可能。答案是两组组合: 1,4 和 2,3。假设封装函数为
从一个数组中找出 N 个数,其和为 M 的所有可能。
举个例子,从数组 [1, 2, 3, 4] 中选取 2 个元素,求和为 5 的所有可能。答案是两组组合: 1,4 和 2,3。
假设封装函数为 search
:
function search(arr, count, sum) { ... return res } 复制代码
则有,
search([1,2,3,4],2,5) // => [[2,3],[1,4]] 复制代码
实现思路
这里我们简单说一下总体思路:根据数组长度构建二进制,再选择其中满足条件的二进制。
我们用 1 和 0 来表示数组中某位元素是否被选中。
比如长度为 4 的所有二进制对应情况是:
- 0000 表示没有选择数组中的任何元素
- 0001 表示选择了数组中第 3 位元素
- 0010 表示选择了数组中第 2 位元素
- 0011 表示选择了数组中第 2、3位元素
- 0100 表示选择了数组中第 1 位元素
- 0101 表示选择了数组中第 1、3 位元素
- 0110 表示选择了数组中第 1、2 位元素
- 0111 表示选择了数组中第 1、2、3 位元素
- 1000 表示选择了数组中第 0 位元素
- 1001 表示选择了数组中第 0、3 位元素
- 1010 表示选择了数组中第 0、2 位元素
- 1011 表示选择了数组中第 0、2、3 位元素
- 1110 表示选择了数组中第 0、1、2 位元素
- 1111 表示选择了数组中所有位元素
那么开篇的例子, 4 选 2,满足条件的二进制有 0011、0101、0110、1001、1010、1100 共 6 种可能。符合元素之和为 5 的最终结果是 0110 和 1001。
看到了吗,思路是我们构建了所有长度为 4 的二进制,再找到符合条件的二进制。
这里条件有两个。
- 其一是,被选中的个数是 2。
- 其二是,被选中的和是 5。
我们的算法思路逐渐清晰起来: 遍历所有二进制,判断选中个数是否 2,然后对应的元素之和,看其是否为 5。
第一个问题,如何遍历所有二进制呢?
这个难不到我们,数组长度为 4,那么所有二进制数据是 0 - 15。
for (var i = 0; i < 16; i++) { ... } 复制代码
第二个问题,如何求取被选中的元素个数呢?即求取二进制字符串中 1 的个数呢?
实现方式有多种,比如其中一种是:
function n(i) { var count = 0; while( i ) { if(i & 1){ ++count; } i >>= 1; } return count; } console.log(n(10)) 复制代码
上述算法的思路其实很简单,将二进制逐步右移 1 位,看看末尾为 1 的个数。比如 10 的二进制是 1010,逐步右移的所有可能是 1010->101->10->1->0,其中有 2 次末尾是 1。因此结果是 2。
第三个问题,如何根据二进制数据来求和呢?
比如 0110,我们应该求和 arr[1] + arr[2]。
问题转化成了如何判断数组下标是否在 0110 中呢?
其实也很简单,比如下标 1 在,而下标 3 不在。我们把 1 转化成 0100,0110 & 0100 为 0100, 大于 0,因此下标 1 在。而 0110 & 0001 为 0,因此 下标 3 不在。
所以求和我们可以如下实现:
var arr = [1,2,3,4] var s = 0, temp = []; for (var i = 0, len = arr.length; i < len; i++) { if ( 0b0110 & 1 << (len - 1 - i)) { s += arr[i] temp.push(arr[i]) } } console.log(temp) // => [2,3] 复制代码
最终实现
有了以上铺垫,这里给出最终实现:
function search(arr, count, sum) { var len = arr.length, res = []; for (var i = 0; i < 1<<len; i++) { if (n(i) == count) { var s = 0, temp = []; for (var j = 0; j < len; j++) { if (i & 1 << (len - 1 -j)) { s += arr[j] temp.push(arr[j]) } } if (s == sum) { res.push(temp) } } } return res; } function n(i) { var count = 0; while( i ) { if(i & 1){ ++count; } i >>= 1; } return count; } console.log(search([1,2,3,4],2,5)) // => [[2,3],[1,4]] 复制代码
本文完。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 找出数组中出现次数超过一半的数
- 算法 - 找出数组中子集乘积的最大值
- 找出数组中第 k 大的数字及其出现次数
- 从一个数组中找出 N 个数,其和为 M 的所有可能--最 nice 的解法
- 用堆找出最小的 N 个数
- MySQL如何找出未提交事务信息
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
An Introduction to the Analysis of Algorithms
Robert Sedgewick、Philippe Flajolet / Addison-Wesley Professional / 1995-12-10 / CAD 67.99
This book is a thorough overview of the primary techniques and models used in the mathematical analysis of algorithms. The first half of the book draws upon classical mathematical material from discre......一起来看看 《An Introduction to the Analysis of Algorithms》 这本书的介绍吧!