改进,从一个数组中找出 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如何找出未提交事务信息
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
人人都是产品经理
苏杰 / 电子工业出版社 / 2010年4月 / 45.00元
这是写给“-1到3岁的产品经理”的书,适合刚入门的产品经理、产品规划师、需求分析师,以及对做产品感兴趣的学生,用户体验、市场运营、技术部门的朋友们,特别是互联网、软件行业。作为一名“4岁的产品经理”,作者讲述了过去3年的经历与体会,与前辈们的书不同,本书就像你走到作者身边,说“嗨哥们!晚上有空吃个饭么,随便聊聊做产品的事吧”,然后作者说“好啊”。 书名叫“人人都是产品经理”,是因为作者觉得过......一起来看看 《人人都是产品经理》 这本书的介绍吧!