leetcode 3315(位运算)

3315: 构造最小位运算数组Ⅱ

题干同leetcode 3314，区别：

• 2 <= nums[i] <= 1000(3314)
• 2 <= nums[i] <= 10^9(3315)

数据规模增大，枚举方法会超出时间限制。

思路：位运算，lowbit

详解见leetcode 3314。

class Solution { public: vector<int> minBitwiseArray(vector<int>& nums) { vector<int> ans(nums.size(),-1); for(int i=0;i<nums.size();i++){ int x=nums[i]; if(x==2) continue; //nums为质数数组，只有2是偶数 int t=~x,s=(t&-t)>>1; //lowbit,右移一位 ans[i]=x^s; } return ans; } };