统计按位或能得到最大值的子集数目（二）

接上文，小编来分享解题思路：

解决方案

方法一：位运算

记 n 是数组 nums 的长度，数组中的每个元素都可以选取或者不选取，因此数组的非空子集数目一共有 (2n-1) 个。可以用一个长度为 n 比特的整数来表示不同的子集，在整数的二进制表示中，n 个比特的值代表了对数组不同元素的取舍。第 i 位值为 1 则表示该子集选取对应元素，第 i 位值为 0 则表示该子集不选取对应元素。求出每个子集的按位或的值，并计算取到最大值时的子集个数。

代码

Python3

class Solution: def countMaxOrSubsets(self, nums: List[int]) -> int: maxOr, cnt = 0, 0 for i in range(1, 1 << len(nums)): orVal = reduce(or_, (num for j, num in enumerate(nums) if (i >> j) & 1), 0) if orVal > maxOr: maxOr, cnt = orVal, 1 elif orVal == maxOr: cnt += 1 return cnt

Java

class Solution { public int countMaxOrSubsets(int[] nums) { int maxOr = 0, cnt = 0; for (int i = 0; i < 1 << nums.length; i++) { int orVal = 0; for (int j = 0; j < nums.length; j++) { if (((i >> j) & 1) == 1) { orVal |= nums[j]; } } if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal == maxOr) { cnt++; } } return cnt; } }

C#

public class Solution { public int CountMaxOrSubsets(int[] nums) { int maxOr = 0, cnt = 0; for (int i = 0; i < 1 << nums.Length; i++) { int orVal = 0; for (int j = 0; j < nums.Length; j++) { if (((i >> j) & 1) == 1) { orVal |= nums[j]; } } if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal == maxOr) { cnt++; } } return cnt; } }

C++

class Solution { public: int countMaxOrSubsets(vector<int>& nums) { int n = nums.size(), maxValue = 0, cnt = 0, stateNumber = 1 << n; for (int i = 0; i < stateNumber; i++) { int cur = 0; for (int j = 0; j < n; j++) { if (((i >> j) & 1) == 1) { cur |= nums[j]; } } if (cur == maxValue) { cnt++; } else if (cur > maxValue) { maxValue = cur; cnt = 1; } } return cnt; } };

复杂度分析

时间复杂度：O(2n×n) ，其中 n 是数组 nums 的长度。需要遍历 O(2n) 个状态，遍历每个状态时需要遍历 O(n) 位。

空间复杂度：O(1) 。仅使用常量空间。