统计按位或能得到最大值的子集数目（二）
接上文小编来分享解题思路解决方案方法一位运算记 n 是数组 nums 的长度数组中的每个元素都可以选取或者不选取因此数组的非空子集数目一共有 (2n-1) 个。可以用一个长度为 n 比特的整数来表示不同的子集在整数的二进制表示中n 个比特的值代表了对数组不同元素的取舍。第 i 位值为 1 则表示该子集选取对应元素第 i 位值为 0 则表示该子集不选取对应元素。求出每个子集的按位或的值并计算取到最大值时的子集个数。代码Python3class 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 cntJavaclass 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; } }Cclass Solution { public: int countMaxOrSubsets(vectorint 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) 。仅使用常量空间。
