深圳建设工程协会网站,免费视频网站建设,做网站的小图标,蚌埠百度做网站982. 按位与为零的三元组
题目描述
给你一个整数数组 nums #xff0c;返回其中 按位与三元组 的数目。
按位与三元组 是由下标 (i, j, k) 组成的三元组#xff0c;并满足下述全部条件#xff1a;
0 i nums.length0 j nums.length0 k num…982. 按位与为零的三元组
题目描述
给你一个整数数组 nums 返回其中 按位与三元组 的数目。
按位与三元组 是由下标 (i, j, k) 组成的三元组并满足下述全部条件
0 i nums.length0 j nums.length0 k nums.lengthnums[i] nums[j] nums[k] 0 其中 表示按位与运算符。 示例 1
输入nums [2,1,3] 输出12 解释可以选出如下 i, j, k 三元组 (i0, j0, k1) : 2 2 1 (i0, j1, k0) : 2 1 2 (i0, j1, k1) : 2 1 1 (i0, j1, k2) : 2 1 3 (i0, j2, k1) : 2 3 1 (i1, j0, k0) : 1 2 2 (i1, j0, k1) : 1 2 1 (i1, j0, k2) : 1 2 3 (i1, j1, k0) : 1 1 2 (i1, j2, k0) : 1 3 2 (i2, j0, k1) : 3 2 1 (i2, j1, k0) : 3 1 2 示例 2
输入nums [0,0,0] 输出27 提示
1 nums.length 10000 nums[i] 216 算法一哈希表 枚举
思路
首先遍历 nums 的前两个值因为题目中提到 0 nums[i] 216 所以我们可以把这两个值按位与的结果存放到哈希表的索引哈希表的值为按位与结果的出现次数这样的时间复杂度为 On2 216 * n 。
收获
我一开始的想法是先计算前两个的值存入数组中然后再遍历数组的值与第三个 num 但其实这样也是 三重循环复杂度也是 On3 显然超时了因此看了题解复杂度可以降到 On2 216 * n。
算法情况 时间复杂度 On2 216 * n其中 n 为 nums.size(); 空间复杂度O2 16
代码
class Solution {
public:int countTriplets(vectorint nums) {int ans 0;vectorint cnt(116);for(int x : nums){for(int y : nums){cnt[x y] ;}}for(int n : nums){for(int i0; i(116); i){if((i n) 0) ans cnt[i];}}return ans;}
};算法二哈希表 枚举优化
思路 算法情况 时间复杂度 O(n(nU))其中 n 为 nums 的长度Umax(nums) 空间复杂度O(U) 。
代码
class Solution {
public:int countTriplets(vectorint nums) {int ans 0;int u1;// 预先计算数组 cnt 的实际大小for(int n : nums){while(u n){u 1;}} vectorint cnt(u);cnt[0] nums.size();for(int n : nums){int m (u-1) ^ n;for(int sm; s; s(s-1)m){cnt[s];}}for(int x : nums){for(int y : nums){ans cnt[x y];}}return ans;}
};参考资料
有技巧的枚举 常数优化Python/Java/C/Go
