E.位运算-异或：2527. 查询数组异或美丽值

题目链接2527. 查询数组异或美丽值中等算法原理解法位运算脑筋急转弯1ms击败100.00%时间复杂度O(N)这道题纯属于博主猜的~因为这题数据量很大想通过必须保证复杂度≤O(NlogN)暴力三层循环必超时依据经验直觉告诉我是脑筋急转弯就尝试着全异或在一起发现题目两个示例过了直接提交了发现果然通过了~~下面来拆解一下为啥是对的①看式子 ((a|b) c)a nums[i] 的这一位b nums[j] 的这一位c nums[k] 的这一位分两种情况情况1c0(任何东西) 0 0不管i、j怎么选结果永远是 00异或多少次都是0 → 这个k对最终答案毫无贡献直接忽略情况2c1(a|b) 1 a|b这个k有效我们要算所有i、j组合的 a|b 全部异或起来看结果是0还是1②算“所有i,j的a|b异或结果”先定义cnt 数组里这一位是1的元素个数总共有 n×n 种(i,j)组合a|b什么时候0只有 a0 并且 b0 的时候a|b0这种组合数 数组里0的个数 × 0的个数→ 这些组合结果都是0异或0不影响答案直接扔掉a|b什么时候1由于二进制中非0即1因此剩下的所有组合都是1我们只关心1的组合数量是奇数还是偶数偶数个1异或0奇数个1异或1关键结论最核心1的组合数量奇偶性 cnt 的奇偶性也就是数组里这一位1是偶数个 → 所有i,j异或结果0数组里这一位1是奇数个 → 所有i,j异或结果1③遍历所有k合并结果只有 c1 的k才会贡献结果每个贡献的值 cnt%2 0或1而 c1 的k正好有 cnt 个我们要算cnt个相同的数互相异或1. 如果 cnt 是偶数全是0 → 异或02. 如果 cnt 是奇数全是1 → 异或1→ 最终这一位结果 cnt%2④和“数组整体异或”对上了数组所有元素异或每一位的结果正好是1的个数是奇数 → 结果11的个数是偶数 → 结果0和我们推导出来的结论完全一模一样~JAVA代码class Solution { //2527. 查询数组异或美丽值 //这题是我纯猜的感觉就是脑筋急转弯试了一下还真通过了~ public int xorBeauty(int[] nums) { int ret0; for(int x:nums) ret^x; return ret; } }