Given a non-repeating prime array arr, and each prime number is used at most once, find all the product without duplicate and sort them from small to large.
2 <= |arr| <= 92 <= arr[i] <= 23Example
Given arr = [2,3], return [6].
Explanation:
2 * 3 = 6.
Gven arr = [2,3,5], return [6,10,15,30].
Explanation:
2 * 3 = 6, 2 * 5 = 10, 3 * 5 = 15, 2 * 3 *5 = 30网上的解法用到了位运算和哈希表来避免重复计算。简单说就是用一个int的各个位来表示当前数组各个素数取舍状态。把这个int值从1开始一直加到2^n即可遍历所有状态了。
不足之处是写起来略繁琐。
这个题目其实可以看作自底向上建立一棵二叉树。每处理一个数，可以看作将当前二叉树复制一份，将当前的数字和1分别作为两个子树的父节点。求积也就是把二叉树从根节点到子节点所有路径遍历一遍。
进一步可以看出，这个过程也就是把当前数字和已有的乘积乘一遍而已。
因为素数本身不能算作乘积，因此不能存在结果数组中，所以我们可以单独处理一遍两个素数相乘的情况，同样加入结果集里。
代码：
vector<int> getPrimeProduct(vector<int> &arr) { vector<int> ans; for(size_t i = 1; i < arr.size(); i++){ size_t len = ans.size(); for(size_t j = 0; j < len; j++){ ans.emplace_back(arr[i] * ans[j]); } for(size_t j = 0; j < i; j++){ ans.emplace_back(arr[j] * arr[i]); } } sort(ans.begin(), ans.end()); return ans; }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。